贪心算法（常见贪心模型）

常见贪心模型

 简单排序模型

最小化战斗力差距

题目分析：

 

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n;
int a[N];int main()
{// 请在此输入您的代码cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);int disparity = 1e9-1;for (int i = 1;i < n;i++) disparity = min(disparity,a[i+1] - a[i]);cout << disparity << '\n';return 0;
}

 货仓选址 

可以发现，仓库建在中间，可以使得货仓到每家商店的距离之和最小

#include <bits/stdc++.h>
using namespace std;const int N = 100010;int n;
int a[N];int main()
{cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);int store = a[n/2 + 1];int res = 0;for (int i = 1;i <= n;i++) {if (i == n/2 + 1) continue;res += abs(store - a[i]);}cout << res << '\n';return 0;
}

总操作一定的情况下的最小代价模型

谈判

如果每次选择代价最小的两个部落合并，不仅可以使得当前代价最小，还可以使得后续合并的代价也尽可能小

局部最优 ==》全局最优

 用数组模拟（O(n^2 log n)）

#include <bits/stdc++.h>
using namespace std;const int N = 1010;int n;
int a[N];int main()
{// 先排序 找到两个人数最少的部落cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);int sum = 0;for (int i = 2;i <= n;i++) {a[i] = a[i] + a[i-1];sum += a[i];sort(a+i,a+1+n);}cout << sum << '\n';return 0;
}

 用优先级队列实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;priority_queue<ll,vector<ll>,greater<ll>> pq;int main()
{//用优先队列实现 每次取其中两个代价最小的部落进行合并，总花费最小int n;cin >> n;for (int i = 1;i <= n;i++){ll x;cin >> x;pq.push(x);}  ll ans = 0;while (pq.size() > 1){ll x = pq.top();pq.pop();ll y = pq.top();pq.pop();ans += x+y;pq.push(x+y);}cout << ans << '\n';return 0;
}

 糖果传递

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1000010;int n;
int a[N];
ll c[N];int main()
{cin >> n;ll sum = 0;for (int i = 1;i <= n;i++) cin >> a[i],sum += a[i];int avg = sum / n;for (int i = n;i > 0;i--) c[i] = c[i+1] + avg - a[i];c[1] = 0;sort(c+1,c+1+n);ll res = 0;for (int i = 1;i <= n;i++) res += abs(c[i] - c[(n+1)/2]);cout << res << '\n';return 0;
}

最少数量的贪心模型

纪念品分组

 

 

 

为了让组数最少，我们要尽可能将两个纪念品打包成一组

怎样的两个纪念品最有可能打包成一组呢，无疑是一个大和一个小的

所以我们先去找最大和最小的，如果不能打包，则去找次小的，直到能打包成一组

不能打包的大的纪念品则单独一组

#include <bits/stdc++.h>
using namespace std;const int N = 30010;int w,n;
int a[N];int main()
{// 请在此输入您的代码cin >> w >> n;int cnt = 0;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);for (int i = 1,j = n;;){if (i > j) break;if (a[i] + a[j] <= w){cnt++;i++,j--;}else {j--;cnt++;}}cout << cnt << '\n';return 0;
}

找规律的贪心模型

分糖果

我们要去使得所有糖果组成的字符串中字典序最大的字符串尽可能小

字符串字典集大小先看首字母大小，其次看后面的字母大小

a < b < c ...

a < aabs...

先给字符串排序，然后分为三类讨论

1️⃣字符串全相等（假设全a），那就尽量使得每个人分到的字符串的最大长度尽可能小，即平分字符串

2️⃣s[x] == s[1] 说明第x个是最小的字符，让它带着后面所有的字符一起输出即可

3️⃣ s[x] != s[1] ,后面一坨字符直接丢到s[1]后面，分给 第一个同学即可

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 10;int n,x;
char s[N];int main()
{// 请在此输入您的代码cin >> n >> x;cin >> s+1;sort(s+1,s+1+n);if (s[1] == s[n]) {for (int i = 1;i <= n / x + (n % x ? 1 : 0);i++) cout << s[i];}else if (s[1] == s[x]) {for (int i = x;i <= n;i++) cout << s[i];}else {cout << s[x];}return 0;
}

股票买卖II

容易发现规律，如果后一天的股票比当天高，那么就今天买入后一天卖出

#include <bits/stdc++.h>
using namespace std;const int N = 1e5 + 10;int n;
int a[N];int main() {cin >> n;for (int i = 1;i <= n;i++) cin >> a[i];int res = 0;for (int i = 1;i <= n;i++){if (a[i] < a[i+1]) res += a[i+1] - a[i];}cout << res << '\n';return 0;
}

乘积最大

 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;const int N = 1e5 + 10,mod = 1000000009;int n,k;
int a[N];int main()
{cin >> n >> k;for (int i = 1;i <= n;i++) cin >> a[i];sort(a+1,a+1+n);int res = 1;int l = 1,r = n;int sign = 1;if (k % 2) {res = a[r--];k--;if (res < 0) sign = -1;}while (k){ll x = (ll)a[l] * a[l+1],y = (ll)a[r] * a[r-1];if (x * sign > y * sign){res = x % mod * res % mod;l += 2;}else {res = y % mod * res % mod;r -= 2;}k -= 2;}cout << res << endl;return 0;
}