Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

堆,为什么平衡树会超时。。。贴AC代码

Posted by yzhw at 2010-09-23 11:10:31 on Problem 2340
# 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator