一道ACM题,很简单,但总是超时
题目http://acm.xmu.edu.cn/JudgeOnline/problem.php?id=1191
我的代码1:
#include<stdio.h>#include<string.h>#define max 1000000int data[max+1];int Min,Max;int GetMin(int pos){ while(data[pos]==0) pos++; return pos;}int GetMax(int pos){ while(data[pos]==0) pos--; return pos;}char orders[6][6]={"RICH","PRICE","ADD","POOR"};char order[6];int main(){ int N,M,i,k,j,t; //freopen("in.txt","r",stdin); scanf("%d%d",&N,&M); for(i=0;i<N;i++) { scanf("%d",&t); data[t]++; } Min=GetMin(0); Max=GetMax(max); for(i=0;i<M;i++) { scanf("%s",order); switch(order[1]) { case 'I': data[Max]--; printf("%d\n",Max); if(data[Max]==0) Max=GetMax(Max); break; case 'R': scanf("%d",&t); if(t<0) { for(k=Min;k<=Max;k++) { data[k+t]=data[k]; } for(k=Max+t+1;k<=Max;k++) data[k]=0; } else { for(k=Max;k>=Min;k--) { data[k+t]=data[k]; } for(k=Min;k<Min+t;k++) data[k]=0; } Min+=t; Max+=t; break; case 'D': scanf("%d",&t); data[t]++; if(t<Min) { Min=t; } else if(t>Max) { Max=t; } break; case 'O': data[Min]--; printf("%d\n",Min); if(data[Min]==0) Min=GetMin(Min); break; } } return 0;}
#include<stdio.h>#include<string.h>#include<deque>#include<iostream>#include<algorithm>using namespace std;#define max 1000000deque<int> deData;deque<int>::iterator iter;char orders[6][6]={"RICH","PRICE","ADD","POOR"};char order[6];int t;bool findx(int n){ return n>t;}int main(){ int N,M,i; //freopen("in.txt","r",stdin); scanf("%d%d",&N,&M); for(i=0;i<N;i++) { scanf("%d",&t); deData.push_back(t); } sort(deData.begin(),deData.end()); //for(iter=deData.begin();iter!=deData.end();++iter) //{ // printf("%d ",*iter); //} //printf("\n"); for(i=0;i<M;i++) { scanf("%s",order); switch(order[1]) { case 'I': printf("%d\n",deData.back()); deData.pop_back(); break; case 'R': scanf("%d",&t); for(iter=deData.begin();iter!=deData.end();++iter) { *iter+=t; } break; case 'D': scanf("%d",&t); if(!deData.empty()) { deData.insert(find_if(deData.begin(),deData.end(),findx),t); } break; case 'O': printf("%d\n",deData.front()); deData.pop_front(); break; } } //printf("\n"); //for(iter=deData.begin();iter!=deData.end();++iter) //{ // printf("%d ",*iter); //} //printf("\n"); return 0;}