前言
贪心算法是两级分化很严重的算法，简单的题目会觉得理所当然，难的题目怎么想也想不出来。与其说是算法，贪心更多的是一种解题的思想，这种思想得具体问题具体分析，因此千变万化没有模板，我们可能上一个贪心题目会写，下一个就不会写了，并且两个题目之间可能没有明显的共同点。有时候，自己想出来的贪心算法是错误的，因此我们需要证明是否正确，但证明的过程一般比较复杂，在时间充裕的时候可以尝试证明。
简单贪心
1. 货仓选址
题目链接:
算法原理
贪心思想：将商店的位置由从小到大排序，然后把货仓建在商店位置的中位数。(证明在后面)
因此如果 n 是奇数，货舱建在 v[(n + 1) / 2] 位置处
如果 n 是偶数，货舱建在 v[n / 2] 到 v[n / 2 + 1] 之间均可
实操代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> v;
while (n--) {
int num;
cin >> num;
v.push_back(num);
}
sort(v.begin(), v.end());
long long ret = 0;
for (int i = 0; i < v.size() / 2 + v.size() % 2; i++) {
ret += v[v.size() - i - 1] - v[i];
}
cout << ret;
return 0;
}
贪心证明
我们假设对于在这个数轴上，有 8 个商店
我们先看 1 和 15
只要我们把货仓建在 1 和 15 的中间，这个货舱距离 1 的距离和 15 的距离之和一定相等
既然 1 和 15 的距离和得到了，我们再看 3 和 13 的距离和，只要货仓在 3 和 13 的中间，距离和就一定是定值 10
我们就这样不停的取最左边和最右边的两个数，只要保证货仓在这两个数字的中间，那么距离和就一定为定值，直到 7 和 10，最后的货仓地址选在 7 和 10 中间，就能保证左右两个商点的距离和等于地址之差的绝对值。
那我不选左右两个值的中间怎么样？很简单，肯定会大于原来的定值的
如果商店个数是奇数的话，直接选择最中间的商店位置即可
之后的贪心算法我们不再证明，因为比较花时间和费脑子。我们在算法竞赛中是不可能有时间去证明你的贪心算法的正确性的，因此我们对于一道贪心题目，得大胆地选择一个方法，就是赌自己想得没有问题，如果赌错了，只能静下心来重新思考了
2. 最大子段和
题目链接:
算法原理
贪心算法:
我们从头遍历数组，保证：当对于每个 right，使得 [left, right] 中的和是以 right 为右边界的所有子段和的最大值
那么这个 [left, right] 的子段和我们可以拆分为 [left, right - 1] + v[right]
我们 right 是从 right - 1 加 1 变过来的，因此对于之前的 right - 1 为右边界的子段和中，[left, right - 1] 已经是最大的了
如果 [left, right - 1] 为负值，那么就是给 right 帮倒忙，之前区间的最大值是个负值，那我还要干什么，因此此时的最大字段和就是 v[right]，随后更新 left = right
如果 [left, right - 1] 为正值，那么最大值是 [left, right]
在具体代码中，我们将 prev 记作 [left, right - 1] 的字段和最大值，一直维护更新即可
实操代码
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> v(n + 1);
for (int i = 1; i <= n; i++) {
long long a;
cin >> a;
v[i] = a;
}
int right = 1;
long long ret = -2e9;
long long prev = 0;
while (right <= n) {
if (prev < 0) {
ret = max(ret, v[right]);
prev = v[right];
} else {
ret = max(ret, prev + v[right]);
prev += v[right];
}
right++;
}
cout << ret;
return 0;
}
3. 纪念品分组
题目链接:
算法原理
贪心算法:
将所有的价格从小到大排序，我们每组先从剩余的价格中选择最大的那个，然后从价格最小的选，一直选，直到拉满要超过上限为止
例如对于样例，排完序后为
20 20 30 50 60 70 80 90 90
第一组：先选 90，然后从最左边的 20 开始选，发现超过了上限，就不要了
剩余：20 20 30 50 60 70 80 90
第二组：先选 90，然后从最左边的 20 开始选，发现超过了上限，就不要了
剩余：20 20 30 50 60 70 80
第三组：先选 80，然后从最左边的 20 开始选，拿一个 20，再拿一个 20 发现超过了上限，就不要了
剩余：20 30 50 60 70
第四组：先选 70，然后从最左边的 20 开始选，拿一个 20，再拿一个 30 发现超过了上限，就不要了
剩余：30 50 60
第五组：先选 60，然后从最左边的 30 开始选，拿一个 30，再拿一个 50 发现超过了上限，就不要了
剩余：50
第六组：直接拿 50
实操代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> v;
while (m--) {
int num;
cin >> num;
v.push_back(num);
}
sort(v.begin(), v.end());
int ret = 0;
int left = 0;
int right = v.size() - 1;
while (left <= right) {
int sum = v[left];
if (sum + v[right] <= n) left++;
ret++;
right--;
}
cout << ret;
return 0;
}
4. 排座椅
题目链接:
算法原理
贪心算法:
由题意可知，设置横向通道不会影响左右相邻的人，设置纵向通道不会影响上下相邻的人
因此我们横向和纵向分别处理
设置横向通道：收集每一条横向通道交头接耳的人的个数，从小到大排序，选择最大的前 K 个
处理纵向通道同理
实操代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
struct node {
int index;
int cnt;
} row[N], col[N];
int m, n, k, l, d;
// 按照 cnt 从大到小排序
bool cmp1(node& x, node& y) {
return x.cnt > y.cnt;
}
// 按照 index 从小到大排序
bool cmp2(node& x, node& y) {
return x.index < y.index;
}
int main() {
cin >> m >> n >> k >> l >> d;
// 初始化结构体数组
for (int i = 1; i <= m; i++) row[i].index = i;
for (int i = 1; i <= n; i++) col[i].index = i;
while (d--) {
int x, y, p, q;
cin >> x >> y >> p >> q;
if (x == p) col[min(y, q)].cnt++;
else row[min(x, p)].cnt++;
}
// 对两个数组按照 cnt 从大到小排序
sort(row + 1, row + 1 + m, cmp1);
sort(col + 1, col + 1 + n, cmp1);
// 对 row 数组，前 k 个元素，按照下标从小到大排序
sort(row + 1, row + 1 + k, cmp2);
// 对 col 数组，前 l 个元素，按照下标从小到大排序
sort(col + 1, col + 1 + l, cmp2);
for (int i = 1; i <= k; i++) {
cout << row[i].index << " ";
}
cout << endl;
for (int i = 1; i <= l; i++) {
cout << col[i].index << " ";
}
cout << endl;
return 0;
}
5. 矩阵消除
题目链接:
算法原理
错误的贪心：每次选择最大的一行或者一列
例如以下矩阵
100 9 1
0 0 0
100 0 2
我们会选择第一列和第二列，然而最佳的选择方法是选择第一行和第二行
正确的贪心:
由于 n 和 m 比较小，因此我们可以无脑枚举
我们先枚举选择列的情况，随后更新数组中的数据，然后在每一行的情况中从大到小选择
实操代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
k = min(k, n + m);
vector<vector<int>> v(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int num;
cin >> num;
v[i][j] = num;
}
}
int ret = 0;
for (int i = 0; i < (1 << n); i++) {
int tmp1 = i;
int count = 0;
vector<int> bit;
for (int j = 0; j < n; j++) {
if ((tmp1 & (1 << j)) != 0) bit.push_back(j);
}
if (bit.size() > k) continue;
auto tmp = v;
int sum = 0;
for (int sz = 0; sz < bit.size(); sz++) {
for (int j = 0; j < m; j++) {
sum += tmp[bit[sz]][j];
tmp[bit[sz]][j] = 0;
}
}
if (bit.size() < k) {
vector<int> y(16, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) y[i] += tmp[j][i];
}
sort(y.begin(), y.end());
auto it = y.rbegin();
for (int i = 0; i < k - bit.size(); i++) {
sum += *it;
it++;
}
}
if (sum > ret) ret = sum;
}
cout << ret;
return 0;
}
