算法竞赛入门经典 训练指南 例题 2

题一样不描述了，这题解题关键在于布置任务的时间是不可能可以省的，主要在于如何省做任务的时间，这就想到了让做任务时间长的工作先布置，这样和接下来布置任务时间重叠，会更加省时间。

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 8 using namespace std; 9 const int MAXN=1007;10 11 int n,t=0;12 13 struct fzy14 {15 int b,j;16 }a[MAXN];17 18 bool cmp(fzy a,fzy b)19 {20 return a.j>b.j;21 }22 int main()23 {24 while (~scanf("%d",&n)&&n)25 {26 t++;27 for (int i=1;i<=n;i++)28 {29 scanf("%d%d",&a[i].b,&a[i].j);30 }31 sort(a+1,a+n+1,cmp);32 33 int ans=0;34 int late[MAXN]={ 0},sum[MAXN]={ 0};35 for (int i=1;i<=n;i++)36 sum[i]=sum[i-1]+a[i].b;37 for (int i=1;i<=n;i++)38 late[i]=sum[i]+a[i].j; 39 40 for (int i=1;i<=n;i++)41 {42 ans=max(ans,late[i]);43 } 44 45 printf("Case %d: %d\n",t,ans);46 }47 }