POJ3045 Cow Acrobats【二分搜索+贪心】

本文主要是介绍POJ3045 Cow Acrobats【二分搜索+贪心】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Cow Acrobats
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 9208 Accepted: 3408

Description

Farmer John’s N (1 <= N <= 50,000) cows (numbered 1…N) are planning to run away and join the circus. Their hoofed feet prevent them from tightrope walking and swinging from the trapeze (and their last attempt at firing a cow out of a cannon met with a dismal failure). Thus, they have decided to practice performing acrobatic stunts.

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

Line 1: A single line with the integer N.
Lines 2…N+1: Line i+1 describes cow i with two space-separated integers, W_i and S_i.

Output

Line 1: A single integer, giving the largest risk of all the cows in any optimal ordering that minimizes the risk.

Sample Input

3
10 3
2 5
3 3

Sample Output

Hint

OUTPUT DETAILS:

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

USACO 2005 November Silver

问题链接：POJ3045 Cow Acrobats
问题简述：有N头牛，给定每头牛的体重和力气。现在N头牛要按顺序排列起来，其中第i头牛的承担风险为前i-1头牛的体重和减去它的力气。要求你任意选择一种序列，使得这N头牛承担的最大风险最小化。
问题分析：最大化最小值问题，可以用二分搜索来做，也可以用贪心来做。
程序说明：（略）
参考链接：（略）
题记：（略）

AC的C++语言程序(二分搜索)如下：

/* POJ3045 Cow Acrobats */#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;const int INF = 0x3f3f3f3f;
const int N = 50000 + 1;
struct Node {int w, s;
} a[N];
bool cmp(Node a, Node b)
{return a.w + a.s < b.w + b.s;
}
int n, sum[N];bool judge(int mid)
{for(int i = 1; i <= n; i++)if(sum[i - 1] - a[i].s > mid) return false;return true;
}int main()
{scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d%d", &a[i].w, &a[i].s);sort(a + 1, a + 1 + n, cmp);sum[0] = 0;int left = INF, right = 0, mid;for(int i = 1; i <= n; i++) {left = min(left, sum[i - 1] - a[i].s);right = max(right, sum[i - 1] - a[i].s);sum[i] = sum[i - 1] + a[i].w;}int ans;while(left <= right) {mid = (left + right) / 2;if(judge(mid)) ans = mid, right = mid - 1;else left = mid + 1;}printf("%d\n", ans);return 0;
}

AC的C++语言程序(贪心)如下：

/* POJ3045 Cow Acrobats */#include <iostream>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 50000;
struct Node {int w, s;
} a[N];
bool cmp(Node a, Node b)
{return a.w + a.s < b.w + b.s;
}int main()
{int n;scanf("%d", &n);for(int i =0; i < n; i++) scanf("%d%d", &a[i].w, &a[i].s);sort(a, a + n, cmp);int sum = 0, ans = -a[0].s;for(int i = 0; i < n - 1; i++) {sum += a[i].w;ans = max(ans, sum - a[i + 1].s);}printf("%d\n", ans);return 0;
}