相邻两个士兵交换顺序,不会对其他的有所影响,贪心考虑两两之间交换策略即可。
sort大法好。印象中这类排序题里有一种会卡sort,只能冒泡排序,然而到现在还没有遇到
/**/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
struct node{
int b;
int j;
};
int cmp(const node a,const node b){
return a.j>b.j;
}
int main(){
int n,b,j;
int case_count=;
while(scanf("%d",&n)!=EOF &&n){
struct node sod[];
int i;
for(i=;i<=n;i++)
scanf("%d%d",&sod[i].b,&sod[i].j);
sort(sod+,sod+n+,cmp);
int s=;
int ans=;
for(i=;i<=n;i++){
s+=sod[i].b;
ans=max(ans,s+sod[i].j);
}
printf("Case %d: %d\n",case_count++,ans);
} return ; }