Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
堆,为什么平衡树会超时。。。贴AC代码# include <cstdio> # include <cstring> # include <queue> # include <cstdlib> # include <vector> using namespace std; priority_queue<int,vector<int>,greater<int> > refer; struct node { int t,num; char op; }; vector<node> data; int main() { char str[100]; for(int i=1;i<=30000;i++) refer.push(i); int c[30001]; memset(c,0,sizeof(c)); while(gets(str)) { node tmp; tmp.t=atoi(strtok(str," ")); tmp.op=*strtok(NULL," "); if(tmp.op=='.') tmp.num=atoi(strtok(NULL," ")); data.push_back(tmp); } int now=0,last=0; for(now=0;now<data.size();now++) { while(data[now].t-data[last].t>=600) { if(c[data[last].num]&&data[now].t-c[data[last].num]>=600) { refer.push(data[last].num); c[data[last].num]=0; } last++; } switch(data[now].op) { case '+': c[refer.top()]=data[now].t; printf("%d\n",refer.top()); data[now].num=refer.top(); refer.pop(); break; case '.': if(c[data[now].num]) { printf("+\n"); c[data[now].num]=data[now].t; } else printf("-\n"); break; }; } //system("pause"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator