> #include <stdio.h>
> #include <string.h>
> #include <iostream> 
> #include <algorithm> 
> using namespace std; 
> typedef struct
> {
>     int w;
>     int d;
> }Order;
> Order a[800001];
> short flag[800001];
> bool cmp(Order x,Order y)
> {
>     return x.d<y.d;
> }
> int main(void)
> {
>     int num,i,j,k;
>     int counter,pos,max;
>     while(scanf("%d",&num)!=EOF)
>     {
>         for(i=0;i<num;i++)
>             scanf("%d%d",&a[i].w,&a[i].d);
>         memset(flag,0,sizeof(flag));
>         counter=num;
>         pos=0;
>         sort(a,a+num,cmp);
>         for(i=0;i<num;i++)
>         {
>             pos+=a[i].w;
>             if(pos>a[i].d)
>             {
>                 max=0;
>                 for(j=0;j<=i;j++)
>                     if((!flag[j])&&a[j].w>max)
>                     {
>                         max=a[j].w;
>                         k=j;
>                     }
>                 flag[k]=1;
>                 pos-=max;
>                 counter--;
>             }
>         }
>         printf("%d\n",counter);
>     }
>     return 0;
> }

• Re:800k^2的计算量吗?? (16) applesun 2008-04-18 13:44:53