算法竞赛入门经典 训练指南 例题 2
题一样不描述了，这题解题关键在于布置任务的时间是不可能可以省的，主要在于如何省做任务的时间，这就想到了让做任务时间长的工作先布置，这样和接下来布置任务时间重叠，会更加省时间。
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #include<cmath> 5 #include<cstring> 6 #include<string> 7 8 using namespace std; 9 const int MAXN=1007; 10 11 int n,t=0; 12 13 struct fzy 14 { 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 ",t,ans); 46 } 47 }