#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;
}

• 800k^2的计算量吗?? (1129) ziliang 2007-09-21 16:08:33
  • Re:800k^2的计算量吗?? (16) applesun 2008-04-18 13:44:53