1057. Stack (30)

时间限制 150 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue

Stack is one of the most fundamental data structures, which is based on the principle of Last In First Out (LIFO). The basic operations include Push (inserting an element onto the top position) and Pop (deleting the top element). Now you are supposed to implement a stack with an extra operation: PeekMedian -- return the median value of all the elements in the stack. With N elements, the median value is defined to be the (N/2)-th smallest element if N is even, or ((N+1)/2)-th if N is odd.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive integer N (<= 10⁵). Then N lines follow, each contains a command in one of the following 3 formats:

Push  key Pop PeekMedian

where key is a positive integer no more than 10⁵.

Output Specification:

For each Push command, insert key into the stack and output nothing. For each Pop or PeekMedian command, print in a line the corresponding returned value. If the command is invalid, print "Invalid" instead.

Sample Input: 17 Pop PeekMedian Push 3 PeekMedian Push 2 PeekMedian Push 1 PeekMedian Pop Pop Push 5 Push 4 PeekMedian Pop Pop Pop Pop Sample Output: Invalid Invalid 3 2 2 1 2 4 4 5 3

Invalid

这题学到了很多。不多说，直接放干货。

试了试最普通的做法，有三个case超时，果然卡了时间。 [cpp]  view plain  copy #include<cstdio>  #include<cstdlib>  #include<cstring>  #include<algorithm>  #define MAX 100005    using namespace std;    typedef struct Stack  {      int data[MAX];      int top;  }Stack;    void Init(Stack *s)  {      s->top=0;  }    void Push(Stack *s,int d)  {      int index=(++s->top);      s->data[index]=d;  }    void Pop(Stack *s)  {      if(s->top==0)      {          printf("Invalid\n");      }      else      {          int d=s->data[s->top];          printf("%d\n",d);          s->top--;      }  }    void PeekMedian(Stack *s)  {      int temp[MAX];      for(int i=1;i<=s->top;i++)          temp[i]=s->data[i];      sort(temp+1,temp+1+s->top);      if(s->top==0)          printf("Invalid\n");      else      {          if((s->top)%2==0)          {              printf("%d\n",temp[(s->top)/2]);          }          else          {              printf("%d\n",temp[(s->top+1)/2]);          }      }  }    int main(int argc,char *argv[])  {      char str[20];      int i,n;      Stack s;      Init(&s);      scanf("%d",&n);      getchar();      for(i=0;i<n;i++)      {          gets(str);          switch (str[1])          {              case 'o':                  Pop(&s);                  break;              case 'e':                  PeekMedian(&s);                  break;              case 'u':                  int num=atoi(&str[5]);                  Push(&s,num);                  break;          }      }      return 0;  }   因为操作中需要不断的求中位数，所以这样复制，排序很自然地导致了超时，改用树状数组就可以AC了； AC代码： [cpp]  view plain  copy #include<cstdio>  #include<cstdlib>  #include<stack>  #define MAX 100005    using namespace std;    int TreeArray[MAX];//树状数组里A[i]的值，表示i出现的次数    int lowbit(int n)  {      return n&(-n);  }    void update(int n,int num)  {      while(n<=MAX)      {          TreeArray[n]+=num;          n+=lowbit(n);      }  }    int GetSum(int n)  {      int sum=0;      while(n>0)      {          sum+=TreeArray[n];          n-=lowbit(n);      }      return sum;  }    int BinSearch(int target)//对栈中间元素进行二分查找，GetSum(mid)返回的值  {                        //表示0~mid之间元素的个数，如果等于target，则mid      int left=0,right=MAX;//就是要求的结果      int mid;      while(left<=right)      {          mid=left+(right-left)/2;          int sum=GetSum(mid);          if(sum>target)              right=mid-1;          else if(sum<target)              left=mid+1;          else if(sum==target)              right=mid-1;   //重要！不能是return sum;可以看我代码的注释    }      return left;  }    int main(int argc,char *argv[])  {      stack<int> s;      char str[20];      int i,n;      scanf("%d",&n);      getchar();      for(i=0;i<n;i++)      {          scanf("%s",str);          switch(str[1])          {              case 'o':                  if(s.empty())                      printf("Invalid\n");                  else                  {                      int key=s.top();                      s.pop();                      printf("%d\n",key);                      update(key,-1);                  }                  break;              case 'u':                  int key;                  scanf("%d",&key);                  s.push(key);                  update(key,1);                  break;              case 'e':                  if(s.empty())                      printf("Invalid\n");                  else                  {                      int midvalue=BinSearch((s.size()+1)/2);                      printf("%d\n",midvalue);                  }                  break;          }      }        return 0;  }   最后发现网上还流传一个比较巧妙的方法，用multiset维护两个集合，这样也可以很快的取出中位数，非常巧妙！！！ AC代码： [cpp]  view plain  copy #include<cstdio>  #include<cstdlib>  #include<set>  #include<stack>  #include<functional>    using namespace std;    stack<int> s;  multiset<int> upper;//大于中位数的数，从小到大排列  multiset<int,greater<int> > lower;//小于中位数的数，从大到小排列  int mid=0;    void Adjust(int* mid)//调整中位数  {      if(upper.size()>lower.size())      {          lower.insert(*upper.begin());          upper.erase(upper.begin());      }      else if(lower.size()>upper.size()+1)      {          upper.insert(*lower.begin());          lower.erase(lower.begin());      }      (*mid)=*lower.begin();  }    int main(int argc,char *argv[])  {      int i,n;      char str[20];      scanf("%d",&n);      getchar();      for(i=0;i<n;i++)      {          scanf("%s",str);          switch(str[1])          {              case 'o':                  if(s.empty())                         printf("Invalid\n");                  else                  {                      int key=s.top();                      s.pop();                      printf("%d\n",key);                      if(key>*lower.begin())                      {                          upper.erase(upper.find(key));                      }                      else                      {                          lower.erase(lower.find(key));                      }                      if(s.empty())                          mid=0;                      else                          Adjust(&mid);                  }                  break;              case 'e':                  if(s.empty())                      printf("Invalid\n");                  else                      printf("%d\n",mid);                  break;              case 'u':                  int key;                  scanf("%d",&key);                  s.push(key);                  if(key>mid)                      upper.insert(key);                  else                      lower.insert(key);                  Adjust(&mid);                  break;          }      }        return 0;  }   下面放我仿的树状数组

#include<string> #include<stdio.h> #include<iostream> #include<string.h> #include<queue> #include<algorithm> #include<map> #include<set> #include<stack> #include<vector> using namespace std; stack<int> S; int cnt[100005]={0}; void updata(int x,int y) { while(x<=100000) { cnt[x]+=y; x+=x&(-x); } } int summ(int x) { int a=0; while(x>0) { a+=cnt[x]; x-=x&(-x); } return a; } int findmid(int sz) { int head=1; int tail=100000; int mid=(head+tail)/2; while(head<=tail) { mid=(head+tail)/2; if(summ(mid)<sz/2) head=mid+1; if(summ(mid)>sz/2) tail=mid-1; if(summ(mid)==sz/2) tail=mid-1; //重要！且不能是return mid；假设有 // 1,5两个元素、则sum(2),sum(3),sum(4)都==sz/2; } return head; } int main() { int n; int p=0; cin>>n; for(int i=0;i<n;i++) { char tmp[15]; scanf("%s",tmp); switch(tmp[1]) { case 'u':int tmp; scanf("%d",&tmp); p++; S.push(tmp); updata(tmp,1); break; case 'o':if(p==0) { printf("Invalid\n");break; } p--; updata(S.top(),-1); printf("%d\n",S.top()); S.pop(); break; case 'e':if(p==0) { printf("Invalid\n");break; } printf("%d\n",findmid(p+1)); break; } } return 0; }