uva11729（Commando War）

想法:贪婪，执行时间长的任务要先解释。按照J从大到小的顺序对每个任务进行排序，然后依次解释。

#include<cstdio>#include<iostream>#include<algorithm>#include<vector>using namespace std;const int maxn = 20000+5;struct Job{int j,b;bool operator<(const Job&x)const{return j>x.j;}};int main(){int n,b,j,cas=1;while (scanf("%d",&n)!=EOF && n){vector<Job>v;for (int i = 0;i<n;i++){scanf("%d%d",&b,&j);v.push_back((Job){j,b});}sort(v.begin(),v.end());int s = 0;int ans = 0;for (int i = 0;i<n;i++){s+=v[i].b;ans=max(ans,s+v[i].j);}printf("Case %d: %d\n",cas++,ans);}}