【习题选讲】贪心

imily's notebook

2020-07-07

贪心

专题助我发现：我贪心弱的一！！！多练！！！

CF1373F

做法一：二分 + 贪心 O(nlogn)（题解做法）

本题单调性体现在哪呢？？显然当第一个电站供应量确定时，所有电站的供应量都确定了

设 b[1] 流给 a[1] 的量为 x

有两种情况：
· “断流”，即 x 太大，导致 b[1] 给 a[2] 供应太少，导致后面断流
· 流一圈后从 b[n] 流回 a[1] 的量加上 x 不 >= a[1]，因为中途可能有点满流

也就是说 x 太大太小都不行，二分传回值标记一下就行了。

做法二：差分约束 O(n)

观察到有很多限制，设 x[i] 表示 b[i] 给 a[i] 的量就可以差分约束，但是 spfa 跑是 n^2 的好像会被卡，，观察建成的图，是一朵菊花的样子，而我们只要判是否有正权环就行，这个可以 O(n) 做。

做法二 Code：

#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 2e6 + 10, inf = 0x3f3f3f3f;
typedef long long ll;
ll T, n, a[N], b[N];

int main() {
    cin >> T;
    while (T--) {
        cin >> n;
        ll tot = 0;
        rep(i, 1, n) scanf("%lld", &a[i]), tot -= a[i];
        rep(i, 1, n) scanf("%lld", &b[i]), tot += b[i];
        if (tot < 0) {
        	puts("NO"); continue;
		}
		bool ff = 1;
		ll mn = b[1], sum = 0;
		rep(i, 1, 2 * n) {
			sum += a[i % n + 1] - b[i % n + 1];
			mn = min(mn, sum + b[i % n + 1]);
			if (sum - mn > 0) {
				ff = 0; break;
			}
		}
        puts(ff ? "YES" : "NO");
    }
    return 0;
}

NOIP2012国王游戏

很经典的题，贪心 + 高精度

邻项交换，微扰可以证明贪心正确性

CF1251E2

考虑选择 x 人时，所有 mi < x 的人都会自动投票，所以将 m 降序排列且降序处理

CF1329C

一句话题意：拿掉元素和尽可能大的同时维护二叉堆性质

我们肯定贪心的取靠近根结点的位置，每个位置取到不能取为止。

什么叫不能取？它扯上来那条链的末尾节点深度为 g 了。所以我们对于每个节点维护链尾节点就好了！

AtCoder-cf17_final_d

https://img.atcoder.jp/cf17-final/editorial.pdf

· 贪心 + dp

关于为什么按 hi + pi 升序排列，官方题解说的很有道理，大致意思就是显然对于高度的限制越松越好，通过邻项微扰来证明贪心正确性。

这边提供另外一种证明：考虑一个合法的选的序列，对于每一个 i 必须满足 sum_{j <= i}{h_j} <= h_i + p_i,
因为前缀和递增所以 hi + pi 也必须递增。

总之是一道很妙的题！

HDU5380

https://www.cnblogs.com/keximeiruguo/p/7684032.html

把糖果视作价格高低不同，就可以贪心了（这题好hard

luogu1484种树

这类问题选择当前最优解时可能不是全局最优解，那怎么办？反悔贪心 可以使得贪心随便选择，都能到达正解。

具体操作用优先队列。对于限制采用缩点（用了 i 就将 l[i]、i、r[i] 缩在一起，反悔了选择了 l[i] 和 r[i] 就将 l[l[i]]、l[i]、i、r[i]、r[r[i]] 缩在一起），反悔就将权值为 val[l[i]] + val[r[i]] - val[i] 的点入队，每次取队首就好了。

SP27102

我们优先格式化 a <= b 的硬盘，按 a 从小到大排序，可以尽量用少的空间来换多的空间，贪心，使得策略最可能成功。

总结：做贪心题直觉很重要，限制越松越好之类的要体会到啊，多练。