題目連結:https://vjudge.net/problem/UVA-11729
跟看電視節目那個基本的貪心一樣,就把執行時間最長的先交代了,這樣就能保證最優解。大白書上有解析這樣的正确性。沒有初始化狀态v搞得WA了四發。。。
/*
* @Author: SamsonHo
* @Date: 2018-09-19-20.10.23
* @URL:https://vjudge.net/problem/UVA-11729
*/
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
const int MAXN = 1e5+10;
struct node
{
int j,b;
bool operator < (const node& x) const
{
return j > x.j;
}
};
vector<node> v;
//bool cmp(pair<int,int> a,pair<int,int> b)
//{
// return a.first > b.first;
//}
int main(void)
{
int n,kase = 0,b,j;
while(~scanf("%d",&n) && n)
{
v.clear();
for(int i = 1; i <= n; ++i)
{
scanf("%d%d",&b,&j);
v.push_back((node){j,b});
}
sort(v.begin(),v.end());
int ans = 0,t = 0;
for(int i = 0; i < n; ++i)
{
t += v[i].b;
ans = max(ans,t+v[i].j);
}
printf("Case %d: %d\n",++kase,ans);
}
}