题目链接:http://poj.org/problem?id=3045
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 5713 | Accepted: 2151 |
Description
The cows aren't terribly creative and have only come up with one acrobatic stunt: standing on top of each other to form a vertical stack of some height. The cows are trying to figure out the order in which they should arrange themselves ithin this stack.
Each of the N cows has an associated weight (1 <= W_i <= 10,000) and strength (1 <= S_i <= 1,000,000,000). The risk of a cow collapsing is equal to the combined weight of all cows on top of her (not including her own weight, of course) minus her strength (so that a stronger cow has a lower risk). Your task is to determine an ordering of the cows that minimizes the greatest risk of collapse for any of the cows.
Input
* Lines 2..N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.
Output
Sample Input
3
10 3
2 5
3 3
Sample Output
2
Hint
Put the cow with weight 10 on the bottom. She will carry the other two cows, so the risk of her collapsing is 2+3-3=2. The other cows have lower risk of collapsing.
Source
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 1e5+; struct node
{
int w, s;
bool operator<(const node &x)const{
return (w+s)<(x.w+x.s);
}
}a[MAXN]; int main()
{
int n;
while(scanf("%d", &n)!=EOF)
{
for(int i = ; i<=n; i++)
scanf("%d%d", &a[i].w, &a[i].s);
sort(a+, a++n);
LL ans = -INF, tot = ;
for(int i = ; i<=n; i++)
{
ans = max(ans, tot-a[i].s);
tot += a[i].w;
}
printf("%lld\n", ans);
}
}