重温贪心

 Tags: OI  Categories: 学习 

恰逢 H 国国庆，国王邀请 位大臣来玩一个有奖游戏。首先，他让每个大臣在左、右手上面分别写下一个整数，国王自己也在左、右手上各写一个整数。然后，让这 位大臣排成一排，国王站在队伍的最前面。排好队后，所有的大臣都会获得国王奖赏的若干金币，每位大臣获得的金币数分别是：排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数，然后向下取整得到的结果。

国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。

---

首先，先画一个草图，

我们要知道 和 到底能不能交换，我们就要比较它们交换前后对他们的贡献值的影响。

我们先假设他们可以交换。故交换后有，

然后我们根据题目，可以计算他们交换前后的值，

由于前面的值不会影响此处 与 对答案的贡献，我们可以直接把连乘消去，

故 与 对答案的贡献可以表示为，

由于我们不难判断，，，故交换前后对答案的贡献变为，

则交换需要满足的条件为 ，通分即为，

故第 项若能与第 项交换，则其左右手之积需大于第 项左右手之积。

bool cmp(node A, node B) {
  /* 这里的 A 相当于第 n + 1 项. */
  return A.a * A.b < B.a * B.b;
}

int main() {
  /* 贪心重新排序. */
  sort(a + 1, a + n + 1, cmp);
}

从上面的题我们可以看出，贪心本质上是假设每一步行动都是最优，且最后结果也是最优。

适用范围：最优子结构问题，即子问题最优解能够递推到总问题最优解；

Last updated: 2025-01-29