NO.64十六届蓝桥杯备战|基础算法-简单贪心|货仓选址|最大子段和|纪念品分组|排座椅|矩阵消除(C++)

贪⼼算法是两极分化很严重的算法。简单的问题会让你觉得理所应当，难⼀点的问题会让你怀疑⼈⽣

什么是贪⼼算法？

贪⼼算法，或者说是贪⼼策略：企图⽤局部最优找出全局最优。

1. 把解决问题的过程分成若⼲步；
2. 解决每⼀步时，都选择"当前看起来最优的"解法；
3. "希望"得到全局的最优解。

贪⼼算法的特点

1. 对于⼤多数题⽬，贪⼼策略的提出并不是很难，难的是证明它是正确的。因为贪⼼算法相较于暴⼒枚举，每⼀步并不是把所有情况都考虑进去，⽽是只考虑当前看起来最优的情况。但是，局部最优并不等于全局最优，所以我们必须要能严谨的证明我们的贪⼼策略是正确的。
   ⼀般证明策略有：反证法，数学归纳法，交换论证法等等。
2. 当问题的场景不同时，贪⼼的策略也会不同。因此，贪⼼策略的提出是没有固定的套路和模板的。我们后⾯讲的题⽬虽然分类，但是⼤家会发现具体的策略还是相差很⼤。因此，不要妄想做⼏道贪⼼题⽬就能遇到⼀个会⼀个。有可能做完50道贪⼼题⽬之后，第51道还是没有任何思路。

如何学习贪⼼？

先有⼀个认知：做了⼏⼗道贪⼼的题⽬，遇到⼀个新的⼜没有思路，这时很正常的现象，把⼼态放平。

1. 前期学习的时候，重点放在各种各样的策略上，把各种策略当成经验来吸收；
2. 在平常学习的时候，我们尽可能的证明⼀下这个贪⼼策略是否正确，这样有利于培养我们严谨的思维。但是在⽐赛中，能想出来⼀个策略就已经不错了，如果再花费⼤量的时间去证明，有点得不偿失。这个时候，如果根据贪⼼策略想出来的若⼲个边界情况都能过的话，就可以尝试去写代码了。

P10452 货仓选址 - 洛谷

将所有的商店按照「从⼩到⼤」的顺序「排序」，把货仓建在中位数处，可以使得货仓到每家商店的距离之和最⼩：

• 如果n是奇数，货仓建在a[(n + 1)/2] 位置处；
• 如果n是偶数，货仓建在a[n/2] ∼ a[n/2 + 1]之间都是可以的

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e5+10;int n;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a+1, a+1+n);LL ret = 0;for (int i = 1; i <= n; i++){//中间位置的下标是(1+n)/2ret += abs(a[i] - a[(1+n) / 2]);}cout << ret << endl;return 0;
}

$$|a-x|+|b-x|\ge |a-b|$$

当x处于两者的中间位置时，左式取得最小值
形如：
$$sum=\sum _{i=1}^n|a[i]-x|=|a[1]-x|+|a[2]-x|+\cdots +|a[n]-x|$$

• 当x 取到n 个数的中位数时，和最⼩；
• 最⼩和为：
  $$(a[n]-a[1])+(a[n-1]-a[2])+...+(a[n+1-n/2]-a[n/2])$$

#include <bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 1e5+10;int n;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a+1, a+1+n);LL ret = 0;for (int i = 1; i <= n/2; i++){ret += abs(a[i] - a[n+1-i]);      }cout << ret << endl;return 0;
}

P1115 最大子段和 - 洛谷

贪⼼想法：从前往后累加，我们会遇到下⾯两种情况：

• ⽬前的累加和>=0：那么当前累加和还会对后续的累加和做出贡献，那我们就继续向后累加，然后更新结果；
• ⽬前的累加和<0：对后续的累加和做不了⼀点贡献，直接⼤胆舍弃计算过的这⼀段，把累加和重置为0，然后继续向后累加。
  这样我们在扫描整个数组⼀遍之后，就能更新出最⼤⼦段和。
  

在累加的过程中算出⼀段区间和sum[a,b]<0 ，如果不舍弃这⼀段，那么[a,b]段之间就会存在⼀点，「以某个位置为起点」就会「更优」，分为下⾯两种情况

1. 在ab段存在⼀个点c ，从这个位置开始，「越过b 」的累加和⽐从a 开始的累加和更优：
   ⽤「反证法」证明这种情况不存在。
   如果存在这⼀点，那么：sum[c, b] > sum[a, b] ，这样才能保证向后加的时候更优。
   但这是「不可能」的。如果sum[c, b] > sum[a, b] ，那么sum[a, c-1]<0，这与我们的贪⼼策略⽭盾。
   因为我们贪⼼策略向后加的时候，只要不⼩于0，就会⼀直加下去。如果[a, c-1]段⼩于0，就
   会在c点之前停⽌，不会累加到b。
   因此区间内不存在⼀点，在计算⼦数组和时，在「越过b 」的情况下，能⽐从a 开始更优。
2. 在ab段存在⼀个点c ，从这个位置开始，「不越过b 」的累加和⽐从a 开始的累加和更优：
   也可以⽤「反证法」证明这种情况不存在。
   如果存在这⼀点，那么：sum[c, k] > sum[a, k] 。
   但这是不可能的。如果sum[c, k] > sum[a, k]，那么sum[a, c - 1] < 0 ，这与我们的贪⼼策略⽭盾。
   因此区间内不存在⼀点，在计算⼦数组和时，在「不越过b 」的情况下，能⽐从a 开始更优。
   综上所述，我们可以⼤胆舍弃这⼀段，重新开始。

#include <bits/stdc++.h>
using namespace std;const int N = 2e5 + 10;typedef long long LL;int n;
LL a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];LL sum = 0, ret = -1e6;for (int i = 1; i <= n; i++){sum += a[i];ret = max(ret, sum);if (sum < 0) sum = 0;}cout << ret << endl;return 0;
}

P1094 [NOIP 2007 普及组] 纪念品分组 - 洛谷

先将所有的纪念品排序，每次拿出当前的最⼩值x 与最⼤值y ：

• 如果x + y ≤ w ：就把这两个放在⼀起；
• 如果x + y > w：说明此时最⼤的和谁都凑不到⼀起，y单独分组，x继续留下在进⾏下⼀次判断。
  直到所有的物品都按照上述规则分配之后，得到的组数就是最优解

可以⽤「交换论证法」证明贪⼼解就是最优解：
对于区间[ai......aj]，如果存在最优解，但是ai与aj的分配⽅式与我们贪⼼解的分配⽅式不⼀样，那么就会有以下⼏种情况：

1. 当a[i] + a[j] > w时：

• 贪⼼解会把a[j]单独分组，a[i]留待下次考虑；
• 最优解也必定会把a[j]单独分组，因为没有更⼩的值与a[j]组合。
  此时贪⼼解与最优解⼀致。

2. 当a[i] + a[j] ≤ w时：

• 贪⼼解会把两者组合分在⼀个组⾥⾯；
• 最优解可能有以下⼏种情况：
  • a[j]单独⼀组：
    • 如果a[i]也单独⼀组的话，最优解还不如贪⼼解分的组少，⽭盾；
    • 如果a[i]和另⼀个a[k]⼀组的话，我们可以把a[k]与a[j]交换，此时并不影响结果，和贪⼼解⼀致。
  • a[j]和a[k]⼀组：
    • 如果a[i]单独⼀组的话，交换a[i]和a[k]，此时并不影响最终结果，和贪⼼解⼀致；
    • 如果a[i]和a[l]⼀组的话，交换a[i]和a[k]，此时变成(a[i]+a[j]),(a[l]+a[k])，其中a[l]+a[k]<=a[j]+a[k]<=w，不影响最终结果，和贪⼼解⼀致。
      综上所述，我们可以通过不断的「调整」，使的最优解在「不改变其最优性」的前提下，变得和贪⼼解⼀致。那我们的贪⼼策略就等价于最优策略。

#include <bits/stdc++.h>
using namespace std;const int N = 3e4 + 10;int w, n;
int a[N];int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> w >> n;for (int i = 1; i <= n; i++) cin >> a[i];sort(a+1, a+1+n);int l = 1, r = n, ret = 0;while (l <= r){if(a[l] + a[r] <= w) l++, r--;else r--;ret++;}cout << ret << endl;return 0;
}

P1056 [NOIP 2008 普及组] 排座椅 - 洛谷

由题意可得，我们会发现⼀些性质：

• 设置横向通道的时候，并「不影响」左右相邻的同学；
• 设置纵向通道的时候，并「不影响」上下相邻的同学。
  因此我们可以「分开」处理横向通道和纵向通道。
  处理横向通道（纵向同理，就不多赘述）：
• 收集每⼀⾏如果放上通道之后，会解决多少个交头接⽿的同学；
• 对收集的信息「从⼤到⼩」排序，选最⼤的k ⾏就是最优结果。

#include <bits/stdc++.h>
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()
{ios::sync_with_stdio(false);cin.tie(0);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;
}

矩阵消除游戏

最优解是先暴⼒枚举所有⾏的选法，在⾏的选择都确定之后，再去贪⼼的处理列

#include <bits/stdc++.h>
using namespace std;const int N = 20;int n, m, k;
int a[N][N];
int col[N]; //统计列和//统计x的二进制中1的个数
int calc(int x)
{int ret = 0;while (x){ret++;x -= x & -x;}return ret;
}//从大到小排序
bool cmp(int a, int b)
{return a > b;
}int main()
{ios::sync_with_stdio(false);cin.tie(0);cin >> n >> m >> k;for (int i = 0; i < n; i++)for (int j = 0; j < m; j++)cin >> a[i][j];int ret = 0;//暴力枚举行所有选法for (int st = 0; st < (1 << n); st++){int cnt = calc(st);if (cnt > k) continue; //不合法memset(col, 0, sizeof col);int sum = 0; //记录当前选法的和for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){if ((st >> i) & 1) sum += a[i][j];else col[j] += a[i][j];}}//处理列sort(col, col + m, cmp);//选k - cnt列for (int j = 0; j < min(k - cnt, m); j++) sum += col[j];ret = max(ret, sum);}cout << ret << endl;return 0;
}