贪心

贪心是一种思想。在对问题求解的过程中，每一步总是做出在当前看来是最好的选择。它不是从整体最优考虑，而是从局部最优考虑。贪心常常使用在求最优解问题中，它是通过求解局部最优，从而达到全局最优。（注意：局部最优，最后不一定全局最优。此时考虑动态规划）

例如：问从塔顶开始，每次可以从一个格子移动到和它相邻的两个格子，求从塔顶到塔底的路径最大值？

贪心的关键：贪心策略

贪心策略基于某种顺序或者规则，一旦做出，就不可以再更改。贪心策略需满足无后效性，即当前的状态不会影响到已经发生的状态。（上面的例子中我们的策略就不是贪心策略）设计出了贪心策略，我们还需要证明。总之：大胆猜测，小心求证

最优装载问题

给出 $n$ 个物体，第 $i$ 个物体的重量为 $w_i$，选择尽量多的物体，使得总重量不超过 $c$。

分析：先把所有物体按重量排序（从小到大排序），然后贪心选择重量比较小的物体直到所选物体的总重量超过所允许的最大重量 $C$。

洛谷 P2240. 部分背包问题

分析：所有金币堆按“单位价格”排序，每次都取最大的那堆，注意，最后一堆有可能只取一部分。

#include <bits/stdc++.h>
using namespace std;

typedef pair<double, double> PII;
const int N = 110;
PII a[N];

bool cmp(PII a, PII b) {
    return a.second > b.second;
}

int main() {
    int n;
	double t;
    cin >> n >> t;

    for(int i = 0; i < n; i++) {
        double m, v;
        cin >> m >> v;
        a[i] = {m, v / m};
    }

    sort(a, a + n, cmp);

    double ans = 0;
	int i = 0;
    for(i = 0; i < n; i++) {
        if(t - a[i].first < -0.000001) { // 剩余的容量不足装第i堆时
        	ans += t * a[i].second;
        	break;
		} else {
		    t -= a[i].first;
        	ans += a[i].first * a[i].second;
		}
    }

    printf("%.2lf\n", ans);

    return 0;
}

洛谷 P1094. 纪念品分组

分析：排序，两端的物体如果能结合就分成一组，否则大的就单独一组。贪心证明：反证法

#include <bits/stdc++.h>
using namespace std;

const int N = 3 * 1e4 + 10;
int a[N];

int main() {
    int w, n;
    cin >> w >> n;

    for(int i = 0; i < n; i++) {
    	cin >> a[i];
	}

    sort(a, a + n);

    int ans = 0, i = 0, j = n - 1;
    while(i < j) {
    	if(a[i] + a[j] <= w) {
    		ans ++;
			i ++;
			j --;
		} else {
			ans ++;
			j --;
		}
	}
	// 剩下单独一件物品
	if(i == j) ans ++;

	cout << ans << endl;

    return 0;
}

洛谷 P1809. 过河问题

分析：

所有人按渡河所需时间从小到大排序。

1. 对于东岸人数 $n==2$ 的情况，很显然，耗费时间为二者中最长的一个，两人即可全部到达对岸

2. 对于 $n==3$ 的情况，先让最快的人带一人去对岸，最快的人回来，再接另一人去对岸，总共花费时间为 $a_1+a_2+a_3$

3. 当 $n>3$，我们假设有东岸有四个人 $p_1,p_2,p_3,p_4$，由样例可知有两种最优的运送方案：

   1. 方案 1：由最快的人 $p_1$ 依次运送 $p_4,p_3,p_2$ 即每一个人。
   2. 方案 2：$p_1,p_2$ 先过河，然后 $p_1$ 回来。$p_3,p_4$ 过河，$p_2$ 回来。

   两种方案最后东岸都会剩下$p_1,p_2$。

   1. 方案 1 的代价：$2p_1+p_3+p_4$
   2. 方案 2 的代价：$p_1+2p_2+p_4$

   我们不确定两种方案的谁最优？min(方案 1，方案 2)

#include <bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N];

int main()
{
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];

    sort(a + 1, a + n + 1);//按用时由小到大排序

    long long ans = 0;
    while(n > 3)
    {
        ans += min(2 * a[1] + a[n] + a[n - 1], a[1] + 2 * a[2] + a[n]); //根据公式累加
        n -= 2; //每次此岸人数减少2人
    }

    if(n==2) ans += a[2]; //此岸人数n为2或3时
    if(n==3) ans += a[1] + a[2] + a[3];

    cout << ans << endl;

    return 0;
}

钱币找零

假设有 1 元、5 元、10 元、20 元、50 元、100 元的纸币分别有 $c_0,c_1,c_2,c_3,c_4,c_5$ 张，现在需要用到这些钱来支付 $K$ 元，至少需要多少张纸币？

ACWing 3648 最少钱币数

分析：每次支付时选取最大的面值进行支付。

const int val[] = {1, 5, 10, 20, 50, 100};
const int count[] = {3, 2, 1, 0, 3, 5};

int solve(int m) {
	int ans = 0;
	for(int i = 5; i >= 0; i--) {
		int c = min(m / val[i], count[i]);
		m -= c * val[i];
		ans += c;
	}

	return ans;
}

洛谷 P1223. 排队接水（单水龙头）

分析：假设 $a_x、a_y$ 两人，在他们之前及之后的都已经按照最优策略确定了顺序，现在要讨论这两人的顺序。

假设接水时间：$a_x<a_y$ 那么有两种顺序：

1. $a_x$ 在前
2. $a_y$ 在前。

这两人的顺序对其他人的等待时间是不影响的。假设其他人的总等待时间为 $sum$，在 $a_x,a_y$ 之前的人的打水时间为 $t$，那么两种方案的总等待时间为:

1. $sum+t+t+a_x$
2. $sum+t+t+a_y$

明显，由前提 $a_x<a_y$ 第一种方案优。即按照打水时间由小到大。这种策略是可以推广到全局。本题的贪心策略：把打水时间少的排在前面。

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> PII;
const int N = 1010;
PII a[N];

bool cmp(PII a, PII b) {
    return a.second < b.second;
}

int main() {
    int n; cin >> n;

    for(int i = 1; i <= n; i++) {
        int t; cin >> t;
        a[i] = {i, t}; // i原来的顺序，t接水时间
    }

    sort(a + 1, a + n + 1, cmp);

    long long ans = 0;
    for(int i = 1; i <= n; i++) {
        cout << a[i].first << " ";
        ans += a[i].second * (n - i);
    }
    cout << endl;

    printf("%.2lf\n", ans * 1.0 / n);

    return 0;
}

提升：如果有多个水龙头呢？洛谷 U305849

分析：总时间 = 打水时间 + 等待时间。打水时间是固定的，因此要求最小的等待时间。根据上一题的分析，按照打水时间由小到大排序，最后的等待时间是最小的。

#include <bits/stdc++.h>
using namespace std;

const int N = 510;
int a[N], b[N]; // a存储每个人的打水时间 b代表每个水龙头上的所有人的打水时间之和

int main()
{
	 int n, r;
	 cin >> n >> r;

	 int ans = 0;
	 for(int i = 1; i <= n; i++) {
		 cin >> a[i];
	 }

	 sort(a + 1, a + n + 1);

	 int t = 1;
	 for(int i = 1; i <= n; i++) {
	 	b[t] += a[i]; // 加上当前人的打水时间和他的等待时间，第一个人的等待时间是0
	 	ans += b[t];  // 这一行不仅加上了第i个人的打水时间还加上了第i个人的等待时间
	 	t = t % r + 1;
	 }

	 cout << ans << endl;

	 return 0;
}

大神排队

现在共有 $n$ 个同学要排成一列,每个同学有两个属性:影响力和承受能力。给一个同学造成的心理创伤指数等于所有在他前面同学的影响力之和减去他的承受能力。请安排一下排队顺序，尽量使受到心理创伤最大的同学少受创伤。

分析：假设队伍中有 $x,y$ 两个人，其中 $a$ 表示影响力，$b$ 表示承受能力。除他们之外的其他人已经排好了队。这两个人的排队顺序不会影响其他人所受到的创伤。我们定义 $sum$ 为之前所有人的影响力之和。

1. 若 $x$ 在前，则 $x$ 受到的伤害为：$sum-b_x$，$y$ 受到的伤害为：$sum+a_x-b_y$。
2. 若 $y$ 在前，则 $x$ 受到的伤害为：$sum+a_y-b_x$，$y$ 受到的伤害为：$sum-b_y$。

由上可知 $x$ 受到的最大伤害为 $max(sum-b_x,sum+a_y-b_x)=sum+a_y-b_x$。$y$ 受到的最大伤害为 $max(sum-b_y,sum+a_x-b_y)=sum+a_x-b_y$，所以我们只需要比较 $sum+a_y-b_x$ 与 $sum+a_x-b_y$ 即可。假设 $sum+a_y-b_x<sum+a_x-b_y$，即 $a_x+b_x<a_y+b_y$。也就是说当$a_x+b_x<a_y+b_y$ 时，$x$ 排在 $y$ 前面更优。

#include <bits/stdc++.h>
using namespace std;

const int N = 50010;

int n,a[N],b[N];
pair<int, int> c[N];

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i];
        c[i].first = a[i] + b[i], c[i].second = i;
    }
    sort(c + 1, c + 1 + n);

    int ans = 0 - b[c[1].second];
    int temp = 0; // 影响力之和
    for (int i = 2; i <= n; i++) {
        temp += a[c[i - 1].second];
        ans = max(ans, temp - b[c[i].second]);
    }
    cout << ans << endl;

    return 0;
}

洛谷 P1115. 最大子段和

分析：当前指针所指元素之前的和小于等于 0，则丢弃当前元素之前的数列。

四种方法：

1. 暴力枚举
2. 前缀和优化
3. 分治
4. 动态规划（贪心）

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int a[N];

int main() {
	int n; cin >> n;

	for(int i = 0; i < n; i++) cin >> a[i];

	int cursum, ans;
	cursum = ans = a[0];
	for(int i = 1; i < n; i++) {
		cursum = max(a[i], cursum + a[i]); // 之前的和加上第i个数之后，还没有第i个数本身大，说明之前的和对答案没有贡献，直接舍弃。这其实就是说当前指针所指元素之前的和小于等于0
		ans = max(cursum, ans);
	}

	cout << ans << endl;

	return 0;
}

YBT 1224. 最大子矩阵

分析：二维前缀和+四重循环

#include <iostream>

using namespace std;

const int N = 1010;
int a[N][N], s[N][N];

int main() {
    int n;
    cin >> n;

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            cin >> a[i][j];
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }

    int ans = s[1][1];
    for(int x1 = 1; x1 <= n; x1++) {
        for(int y1 = 1; y1 <= n; y1++) {
            for(int x2 = x1; x2 <= n; x2++) {
                for(int y2 = y1; y2 <= n; y2++) {
                    int t = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
                    ans = max(ans, t);
                }
            }
        }
    }

    cout << ans << endl;

    return 0;
}

洛谷 P1106. 删数问题

分析：每次循环从高位开始寻找递减区间，将递减区间的第一个数删去，若各位数字递增则删除递增区间的最后一个数字。注意前导零！

#include <bits/stdc++.h>
using namespace std;

int main() {
	string s;
	int n;
	cin >> s >> n;

	for (int i = 0; i < n; i++) {
		bool flag = false;
		// 删除递减区间第一个
		for (int j = 1; j < s.length(); j++) {
			if (s[j - 1] > s[j]) {
				s.erase(j - 1, 1);
				flag = true;
				break;
			}
		}
		// 该趟删数并未找到递减区间，则删除递增区间最后一个
		if (!flag) s.erase(s.length() - 1, 1);
	}

	// 可能存在前导零的情况
	while (s.length() > 1 && s.front() == '0') s.erase(0, 1);

	cout << s << endl;

	return 0;
}

洛谷 P1012. 拼数

分析：首先，自然会想到大的字符串应该排在前面，因为如果 $A$ 与 $B$ 是两个由数字字符构成的字符串，且 $A>B$，一般情况下有 $A+B>B+A$。但是，也存在特殊情况。如 A= "121"，B = "12" ，则 A + B= "12112"，B + A = "12121"，所以 $A+B<B+A$。

为了解决这个问题，根据题意引进另一种字符串比较办法，将 $A+B$ 与 $B+A$ 相比较，如果前者大于后者，则认为 $A>B$。按这一定义将所有的数字字符串从大到小排序后连接起来所得到的数字字符串即是问题的解。

#include <bits/stdc++.h>
using namespace std;

const int N = 25;
string a[N];

bool cmp(string a, string b) {
    return a + b > b + a;
}

int main() {
    int n;
    cin >> n;

    for(int i = 0; i < n; i++) cin >> a[i];

    sort(a, a + n, cmp);

    for(int i = 0; i < n; i++) cout << a[i];
    cout << endl;

    return 0;
}

洛谷 P1031. 均分纸牌

分析：首先我们确定，最后一定能平均分。在手推样例的过程中，能发现最优的移动顺序满足两堆之间最多移动一次。将每堆牌都减去平均数，得到一个有正有负的数列。贪心策略：从左到右扫描，如果该数为正，将他右边的数加上该数的绝对值，同时该数变为 $0$。如果该数为负，将他右边的数减去该数的绝对值，该数变为 $0$。如果扫描遇到的数为 $0$，直接跳过。计数就可以了。进一步分析发现，其实负数也可以移动。这样就不用分正负数了，直接将该数右边的数加上该数，该数变为 $0$ 就可以了。复杂度 $O(n)$

#include <iostream>
using namespace std;

const int N = 110;
int a[N];

int main() {
    int n; cin >> n;

    int sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }

    int avg = sum / n;
    for(int i = 0; i < n; i++) a[i] -= avg;

    int i = 0, ans = 0;
    while(i < n - 1) {
        if(a[i]) {
            a[i + 1] += a[i];
            a[i] = 0;
            ans++;
        }
        i++;
    }

    cout << ans << endl;

    return 0;
}

洛谷 P1020. 导弹拦截

分析：如果是第一个导弹，肯定需要一套系统。对于后面的导弹，如果当前所有系统满足不了它，就增加系统，否则从当前所有系统中把能打高度最低但是大于该导弹高度的系统分配给它。扫描一遍即可。复杂度 $O(n)$。$h$ 数组记录每个拦截系统的最大高度。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], h[N], n, f[N];

int main() {
	while(cin >> a[++n]);
	n--;

    int cnt = 0, ans = 0;
	for (int i = 1; i <= n; i++) {
        f[i] = 1;
        for (int j = 1; j < i; j++) {
            if (a[i] <= a[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans = max(ans, f[i]);

        int k = 0;
		while(k < cnt && h[k] < a[i]) k++;
		if (k == cnt) h[cnt++] = a[i];
		else h[k] = a[i];
	}

	cout << ans << endl;
	cout << cnt << endl;

	return 0;
}

区间类问题

AcWing 908. 最大不相交区间数量

练习题：YBT 1323. 活动选择

分析：

1. 将每个区间按右端点从小到大排序。
2. 从前往后枚举每一个区间，如果当前区间和已选区间冲突，直接 pass，否则将当前区间加入已选区间。

#include <bits/stdc++.h>
#define r first
#define l second
using namespace std;

typedef pair<int, int> PII;
const int N = 1e5 + 10;
PII a[N];

int main() {
    int n; cin >> n;

    for(int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        a[i] = {r, l};
    }

    sort(a, a + n);


    PII last = a[0]; // 已选区间的最后一个区间
    int cnt = 1;
    for(int i = 1; i < n; i++) {
        if(a[i].l > last.r) { // 当前区间和last不相交
            last = a[i];
            cnt++;
        }
    }
    cout << cnt << endl;

    return 0;
}

AcWing 905. 区间选点

练习题：

1. YBT 1324. 整数区间
2. AcWing 112. 雷达设备

分析：

1. 将每个区间按右端点从小到大排序。
2. 从前往后枚举每一个区间，如果当前区间已包含点，直接 pass，否则选择当前区间的右端点。

• 代码和上一题一模一样，不需要改。

AcWing 907. 区间覆盖

分析：

1. 将所有区间按左端点从小到大排序。
2. 从前往后依次枚举每一个区间，在所有能覆盖 start 的区间中，选择右端点最大的区间，然后将 start 更新成右端点的最大值。

#include <bits/stdc++.h>
#define l first
#define r second
using namespace std;

typedef pair<int, int> PII;

const int N = 1e5 + 10;
PII a[N];

int main() {
    int s, t, n; cin >> s >> t >> n;

    for(int i = 0; i < n; i++) {
        int l, r;
        cin >> l >> r;
        a[i] = {l, r};
    }

	sort(a, a + n);

   int res = 0, flag = false;
   for(int i = 0; i < n; i++) {
       int j = i, r = -1e9;
       while(j < n && a[j].l <= s) {
           r = max(r, a[j].r);
           j++;
       }
       if(r < s) break;

       res++;
       if(r >= t){
           flag = true;
           break;
       }

       s = r;
       i = j - 1;
    }

    if(flag) cout << res << endl;
    else cout << -1 << endl;

    return 0;
}

AcWing 906. 区间分组

练习题：

1. AcWing 111. 畜栏预定

分析：

1. 将所有区间按左端点从小到达排序
2. 从前往后处理每个区间，如果当前区间可以加入之前某组，则加入并更新该组，否则创建新组并加入。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct Node {
    int l, r;
    bool operator < (const Node &a) const {
        return l < a.l;
    }
} a[N];

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i].l >> a[i].r;
    }
    sort(a, a + n);

    priority_queue<int, vector<int>, greater<int>> q;
    for (int i = 0; i < n; i++) {
        if (q.empty() || q.top() >= a[i].l) q.push(a[i].r);
        else {
            q.pop();
            q.push(a[i].r);
        }
    }

    cout << q.size() << endl;

    return 0;
}

Huffman 树

AcWing 148. 合并果子

其他问题

神奇的宝物

某一岛屿上有 $n(n\le 100000)$ 种宝物，每种宝物只有两件(所以只有两个寻宝者来的时候才能看见)，两位寻宝者轮流取宝物，每个宝物每个人只能取一次。神奇的是，第 $i$ 种宝物先取的人获得的价值为 $a_i$，后取的人获得的价值为 $b_i$，其中 $1\le b_i\le a_i\le {10}^9$。两位寻宝者都想自己获得的价值最大，他们都学过中国一句俗话“先下手为强”，于是为了谁先下手取宝物争论不休，你能帮他们计算出先下手和后下手获得的总价值吗？

样例 #1

2 // 宝物种类 n
2 1 // 先下手价值 a 后下手价值 b
5 3

6 5

解释：不妨设这两个人为 $A$ 和 $B$，让 $A$ 先下手。$A$ 首先取第 $2$ 件宝物，获得价值 $5$，那么 $B$ 为了自己利益最大化，取第 $1$ 件宝物，获得价值 $2$，那么接下来 $A$ 只能取第 $1$ 件宝物，获得价值 $1$，最后 $B$ 只能取第 $2$ 件宝物，获得价值 $3$。

样例 #2

5
9 7
10 5
10 1
6 5
7 6

36 30

分析：每个物品我们只需要考虑谁先来取即可，先取一旦确定，后取自然确定。因为宝物的总价值是固定的，同时每种宝物的总价值也是固定的，并且 $A$ 和 $B$ 各分一个。所以站在每个人的角度上，若想让总价值最大，那么肯定要尽可能先取，而且要让对方的价值尽可能小，所以进行先取时，优先取择价值差别大的。对宝物按照 $a_i-b_i$ 的差值从大到小排序，依次确定先取即可。

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
struct Node {
	int a, b;
} a[N];

bool cmp(Node &a, Node &b) {
	return a.a - a.b > b.a - b.b;
}

int main() {
	int n; cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i].a >> a[i].b;
	sort(a + 1, a + n + 1, cmp);

	long long x = 0, y = 0;
	for (int i = 1; i <= n; i++) {
		if (i % 2) x += a[i].a, y += a[i].b; // A先
		else x += a[i].b, y += a[i].a; // B 先
	}
	cout << x << " " << y << endl;

	return 0;
}

课后习题

1. 洛谷 P1803. 凌乱的 yyy
2. 洛谷 P3817. 小 A 的糖果
3. 洛谷 P1478. 陶陶摘苹果升级版
4. 洛谷 P5019. 铺设道路
5. 洛谷 P4995. 跳跳！
6. 洛谷 P1208. 混合牛奶
7. 洛谷 P4447. 分组
8. 洛谷 P1080. 国王游戏