首页 > 代码库 > PAT 1057. Stack (30)
PAT 1057. Stack (30)
题目地址:http://pat.zju.edu.cn/contests/pat-a-practise/1057
用树状数组和二分搜索解决,对于这种对时间复杂度要求高的题目,用C的输入输出显然更好
#include <cstdio> #include <string> #include <vector> #include <stack> using namespace std; const int NUM=100001; struct TreeArray { vector<int> cStore; TreeArray() { cStore=vector<int>(NUM,0); } int lowerBit(int x) { return x&(-x); } void add(int location,int addedValue) { while(location<=NUM) { cStore[location]+=addedValue; location+=lowerBit(location); } } int getSum(int location) { int sum(0); while(location>0) { sum+=cStore[location]; location-=lowerBit(location); } return sum; } int findMedian(int toFind,int low=1,int high=NUM) { if(low==high) return low; int median=(low+high)>>1; if(getSum(median)<toFind) { return findMedian(toFind,median+1,high); } else { return findMedian(toFind,low,median); } } }; TreeArray treeArray; stack<int> s; int _tmain(int argc, _TCHAR* argv[]) { int N; scanf("%d",&N); char command[20]; int key; for(int i=0;i<N;++i) { scanf("%s",command); switch(command[1]) { case ‘u‘: scanf("%d",&key); s.push(key); treeArray.add(key,1); break; case ‘e‘: if(s.empty()) printf("Invalid\n"); else { printf("%d\n",treeArray.findMedian((s.size()+1)/2)); } break; case ‘o‘: if(s.empty()) printf("Invalid\n"); else { key=s.top(); s.pop(); printf("%d\n",key); treeArray.add(key,-1); break; } } } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。