POJ 3045 Cow Acrobats 二分+优先队列

一、题目大意

题目中给出了N头牛，这些牛要互相叠罗汉，牛i承担的风险risk[i]为牛i上面的牛的质量之和sum[i]（如果上面没有牛就是0）减去牛i的力量strength[i]，即risk[i]=sum[i]-strength[i]

我们要优化这个叠罗汉的顺序，使得1-N头牛的风险值中的最大值，最小。

二、解题思路

这个题目要对风险值进行二分

首先我们设牛i的质量为weight[i]，牛i的力量为strength[i]，风险值为mid，所有牛的质量之和为sum，按叠罗汉顺序从下往上数最底下一头牛为first，倒数第二头牛为second，第三个为third，那么有如下表达式。

sum-weight[first]-strength[first]<=mid
sum-weight[first]-weight[second]-strength[second]<=mid
sum-weight[first]-weight[second]-weight[third]-strength[third]<=mid

不难看出，我们让顺序靠下的牛在满足条件的情况下，质量尽可能大，那么就缓解了顺序靠上的牛的压力。

所以题目对风险值进行二分，然后判断风险值是否可行，如果可行，则缩小风险值，如果不可行，则放大风险值，输出最后一次满足条件的风险值即可。

判断的过程的思路来自于上面的表达式，如果我们让底下的牛的质量尽可能大，那么对顶上的牛的力量的要求就不会那么严苛。判断过程中进行N次循环，每次找到满足 当前剩余牛的重量-牛i的重量-牛i的力量<=mid 条件的所有牛i，放入到优先队列中，取出质量最大的放在底下，同时更新剩余牛的重量，然后继续下次循环，如果优先队列为空了，那么代表我们找不到满足条件的牛i，则mid过小，返回false，N次循环正常结束，则mid可行。（需要注意的是要避免优先队列放入重复的元素）

三、代码

代码这里为了防止中途计算溢出，对mid开了一个long long，对于本题目的数据其实可以不开。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
struct Cow
{int weight, strength;Cow(int weight = 0, int strength = 0) : weight(weight), strength(strength) {}
};
int N;
Cow cows[50007];
int inf = 0x3f3f3f3f, weightSum = 0;
bool operator<(const Cow &a, const Cow &b)
{return a.weight < b.weight;
}
bool compare(const Cow &a, const Cow &b)
{return (a.strength + a.weight) < (b.strength + b.weight);
}
void input()
{scanf("%d", &N);for (int i = 0; i < N; i++){scanf("%d%d", &cows[i].weight, &cows[i].strength);weightSum += cows[i].weight;}sort(cows, cows + N, compare);cows[N] = Cow(0, inf);
}
// 判断最小风险mid是否可行
bool judge(int mid)
{priority_queue<Cow> que;int right = N, currentSum = weightSum;for (int i = 0; i < N; i++){int next = lower_bound(cows, cows + N + 1, Cow(currentSum - mid, 0), compare) - cows;for (int j = next; j < right; j++){que.push(cows[j]);}right = next;if (que.empty()){return false;}Cow cow = que.top();que.pop();currentSum -= cow.weight;}return true;
}
void binarySearch()
{int left = -1000000001, right = weightSum;while (left + 1 < right){ll mid = left;mid += right;mid = mid >> 1;if (judge((int)mid)){right = (int)mid;}else{left = (int)mid;}}printf("%d\n", right);
}
int main()
{input();binarySearch();return 0;
}