csp知识基础——贪心算法
核心原则：局部最优会导致全局最优
用几个题目来感受一下：
t1接水问题和t2导弹拦截方案
t1：多水龙头接水
有n个人，每个人打水时间不一样，但打水顺序已经定了，一共m个水龙头，求总用时最短。
输入：
5 3
4 4 1 2 1输出：
4
一开始，我理解错了，我以为打水顺序可以变，所以先排序再安排打水，因为打水时间=接水时间+排队时间，所以在每个人接水时间固定下，让排队时间最小即可。输出结果一直不对，最后问了AI才发现自己粗心没看到说排队时间已经固定。。。
解析：第一波打水 4 4 1，下面就是,
2去了（4 4 1）中的三号位，用时1+2=3，
1去了（4 4 3）中的三号位，用时3+1=4
所以关键就是找到并更新最小打水时间，用优先队列的方法比较好，复习一下优先队列的用法：
1，priority_queue< int > a; // 基础类型, 默认是大顶堆，自动排
2，priority_queue<int, vector< int >, greater< int > > c; //基础类型，变小根堆
#include <bits/stdc++.h>
using namespace std;
using ll = long long;int main() {int n, m;cin >> n >> m;vector<int> w(n);for (int i = 0; i < n; i++) cin >> w[i];// 小根堆存水龙头结束时间priority_queue<ll, vector<ll>, greater<ll>> pq;// 先让前 m 个人上for (int i = 0; i < m; i++) {pq.push(w[i]);}// 后续的人找最早空闲的水龙头for (int i = m; i < n; i++) {ll t = pq.top(); pq.pop();pq.push(t + w[i]);}// 最后的答案是最大结束时间ll ans = 0;while (!pq.empty()) {ans = max(ans, pq.top());pq.pop();}cout << ans << "\n";return 0;
}然后后面是我自己的方法，不符合题意的那种。。。但也敲了好久，我最后输出数据表示，这个总用时比上面的方法还要长，这我就不太理解了。。。有懂的大佬可以回复一下嘛。。
#include <bits/stdc++.h>
#define ll long long
using namespace std;int main() {ll n;int m; // n 人，m 个水龙头cin >> n >> m;vector<ll> a(n+1);for (ll i = 1; i <= n; i++) cin >> a[i];sort(a.begin() + 1, a.end()); // 时间短的先打，理解错了题意//求最短打水时间 已知每个人的时间是 排队时间+打水时间，那么让排队时间最短即可。即//1.先排序，按时间大小进行排序//2.计算每个人的打水时间，第一波人，时间=打水时间；第二波人，时间=排队时间（第一波人时间）+打水时间//3....依次计算出最后那个人的打水时间//4.发现规律：第m+1个人在第1个后面，即1~m+1~2m+1...,2~m+2~2m+2...所以，要想知道最后一个人的打水时间，只需要看他是第几组即可if (n <= m) { // 一波打完cout << a[n] << endl;return 0;}// 最后一个人的列位置 (从 1 开始)int col = (n - 1) % m + 1;ll ans = 0;// 同一列上的人： col, col+m, col+2m, ...for (ll i = col; i <= n; i += m) {ans += a[i];}cout << ans << endl;
}t2：导弹拦截方案
我理解的意思是：炮弹的发送顺序已经确定，现在用一个系统墙壁进行防御，每次会打坏上面的部分，即假设系统1初始高度>=389,在第一发过来之后，高度就变成了=389，第二发过来之后，高度就变成了207，第三发过来后就变成了175，那么第四发300过来，系统1（175）明显挡不住了，就需要在后面加一套系统，我们叫他系统2防御墙（>=300），它阻挡第四发300后，变成了300，第五发299也得系统2（300）来挡，系统2变成了299，第六发170可以被系统1（175）挡住，即系统1变成170，第七发158还是可以被系统1（170）挡住，变成158，最后一发165，就只能被系统2（299）挡住了，，，问题本质上是最少非递增子序列划分问题，贪心就是每次把导弹分到最合适的现有系统里。
所以一共需要两套系统，每套系统可以阻拦的炮弹也如上图所示，该题的做法就是不断更新系统能拦截的最大高度，不能拦截就再加一套系统，继续从头遍历系统，能拦截就拦截，不能就加一套系统。。。
#include <bits/stdc++.h>
using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(nullptr);int h;vector<int> missiles;while (cin >> h) { // 读到输入结束missiles.push_back(h);}struct System {int height; // 当前系统可拦的最大高度vector<int> sequence; // 该系统拦下的导弹序列};vector<System> systems;for (int m : missiles) {bool blocked = false;for (auto &sys : systems) {if (sys.height >= m) { // 该系统可以拦sys.height = m; // 更新高度sys.sequence.push_back(m);blocked = true;break;}}if (!blocked) { // 新建系统systems.push_back({m, {m}});}}cout << systems.size() << "\n"; // 输出最少系统数for (size_t i = 0; i < systems.size(); i++) {cout << "系统 " << (i + 1) << " : 拦截 ";for (size_t j = 0; j < systems[i].sequence.size(); j++) {cout << systems[i].sequence[j];if (j + 1 < systems[i].sequence.size()) cout << " ";}cout << "\n";}return 0;
}