Democy 爷给了一份贪心的题单，但是由于我是小笨比，所以很多题我都不是很会做，现在来简单写一份总结，加强一下印象 qwq。
首先什么叫贪心？贪心就是我每次都选择一个最大值。比如说我现在有 \(n\) 个物品，每个物品都有一个价值，我们可以选 \(k\) 件物品，我们怎么样让选择的价值和最大呢？傻子都知道我们要选最大的 \(k\) 个。这就是贪心。
贪心还有很多有趣的地方的说 qwq。
由于我贪心真的很差，所以我可能要拆成三篇写这份题单的报告 awa
反悔贪心
我在网上查了一下反悔贪心的资料，比如这个这个，什么反悔堆反悔自动机的把我看蒙了。我觉得这个东西有一说一全属胡扯八道，完全就是照着题目写模型，比如说啥“双向链表模型啊”完全没有这档子事，是我先有了反悔贪心，然后为了维护反悔贪心，然后才会用堆啊双向链表。我觉得这就是对反悔贪心的理解不透彻，虽然我自个儿理解的也不是很好。这段话语气有点冲希望大家不要怼我（
一句题外话：我之前问了问 democy 爷反悔贪心怎么证明，据说这个要用拟阵，它有一个最优子结构性质在，但是这个东西不适合幼儿园小朋友学习。总结就是你觉得这个反悔贪心看上去很对然后你就可以这么写。（雾
那么反悔贪心是啥，就是有的时候我们贪心不一定是最优解，然后我们允许我们反悔撤销操作来得到最优解。怎么证明似乎要用拟阵，总而言之我不会，就是觉得能用就行。毕竟 OI 是一门没有证明的艺术（雾）。它怎么写？看几道题就明白了。贪心不也一样吗，没有一定的方法套路。
P3545
我们会想到两个贪心策略
- 多卖，满足客户要求。
- 库存要多
其中，第一个策略是我们要尽量满足的，因为它是答案。第二个策略是为了辅助我们的第一个策略的。有时我们一味的满足第一个条件可能不是最优的选择，比如第一天进了 100 个货，客户要 100 个，第二天第三天都没进，客户只要 1 个货。如果我们只按照 1 的策略，我们就只能满足 1 个人，但是实际上我们可以满足 2 个人。
所以聪明的你就会想到，在贪心中加入一个反悔操作。我们可以把卖 100 个给第一个人这个决策放到一个篮子里面，然后我下面如果能卖就卖（满足条件 1），如果卖不掉呢，我们就考虑反悔，看看如果我们之前不和某个人交易，如果我之前交易的比现在的需求量大，我还不如用之前交易的来满足现在的需，然后把之前满足的“退单”，因为这样我的答案加一减一后不会变，而且库存会变多。这个篮子用啥？很显然，用大根堆。
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define MAXN 250000
#define int long long
#define QWQ cout << "QWQ" << endl;
using namespace std;
struct node {
long long val;
int id;
node(long long V, int I) {
val = V, id = I;
}
bool operator < (const node &other) const {
return val < other.val;
}
};
vector <int> vec;
long long a[MAXN + 10], b[MAXN + 10];
bool vis[MAXN + 10];
signed main() {
priority_queue <node> que;
int n; cin >> n;
for(int p = 1; p <= n; p++)
cin >> a[p];
long long ans = 0, tot = 0;
for(int p = 1; p <= n; p++) {
cin >> b[p];
tot += a[p];
if(tot >= b[p]) {
tot -= b[p];
que.push(node(b[p], p));
ans++;
}
else if(!que.empty() && que.top().val > b[p]) {
tot = tot + que.top().val - b[p];
que.pop(); que.push(node(b[p], p));
}
}
while(!que.empty()) {
vec.push_back(que.top().id);
que.pop();
}
sort(vec.begin(), vec.end());
cout << ans << endl;
for(int p = 0; p < ans; p++)
cout << vec[p] << ' ';
}
上面讲的有点抽象，看看代码就懂了 awa
顺带一提，我之前有一个问题 link
这个问题是怎么回事你，就是说我把反悔贪心的判断写成了酱紫 else if(!que.empty() && tot + que.top().val >= b[p]) {
然后我就 WA 了。这很好解释。反悔的目的在于让库存变多。但是如果用剩下的+之前的订单>=需求量，就可能会出现之前的订单<需求量的情况。如果是这种情况，库存会变少，不能反悔。这告诉我们反悔要仔细想一想判断条件是不是满足反悔要求。
还有一个朋友提出了酱紫的一个问题 link，就是说如果我每个客户有个满意度，我让满意度最大，那么这还能做吗？我觉得不能。我在帖子下也回复了，现在 copy 过来（
因为这道题我贪心要有两个策略
- 多卖，满足客户要求。
- 库存要多
第一个策略要尽量满足，是我们要求的答案，第二个策略是为了第一个策略来制定的，有时候一味的第一个策略不是正确答案，就需要第二个策略来制约。具体可以这么感性理解，怎么证明窝不会，好像要用拟阵反正窝不会，OI 不需要证明（
反悔贪心的反悔建立在 1 2 的共同基础上。反悔反悔什么，反悔在于我之前的决策价值是 1，我反悔后的决策价值也是 1。这样 1 条件是满足的（不会变坏），如果我反悔，我可以让 2 条件更好，所以我会这样做。但是如果带权，1 条件就不一定可以满足，所以我不能反悔贪心。
P2209
经典的旅行商问题！
看到这个问题，第一个想法就是在每个加油站把所有的油给油箱加满，但是这很明显是错的，首先我可能用不完，其次我可能就是刚好用现在有的油走到下一站，然后我用下一站更便宜的油来加。
第一个问题很好解决，只在“走”的时候累加油的费用。第二个问题怎么解决？由于每个站可以无限加油，所以我们可以这样看待我们的油箱：它是分层的，我们每次都用费用最小的油，旅行到下一个站的时候，如果这个站的油很便宜，那么就把油箱里面的所有贵的油退掉。现在的问题就是怎么维护这个油箱。这个退油操作很容易让我们联想到单调队列，是的，我们可以用单调队列维护，时间复杂度 \(O(n)\)。
#include <bits/stdc++.h>
#define int long long
#define QWQ cout << "qwq" << endl;
using namespace std;
const int MAXN = 1e5;
struct node {
int x, y;
bool operator < (const node &other) const {
return x < other.x;
}
} A[MAXN + 10], que[MAXN + 10];
int n, G, B, D;
void init() {
int head = 1, tail = 1;
cin >> n >> G >> B >> D;
A[1].x = 0, A[1].y = 0;
for(int p = 2; p <= n + 1; p++)
cin >> A[p].x >> A[p].y;
A[n + 2].x = D, A[n + 2].y = 0, n += 2;
sort(A + 1, A + n + 1);
que[1].x = 0, que[1].y = B;
int cost = 0;
for(int p = 2; p <= n; p++) {
int dist = abs(A[p].x - A[p - 1].x);
while(head <= tail) {
if(que[head].y < dist) {
cost += que[head].x * que[head].y;
dist -= que[head].y;
head++;
}
else {
cost += dist * que[head].x;
que[head].y -= dist;
dist = 0;
break;
}
}
if(dist) {
cout << -1 << endl;
return ;
}
int num = ((p == 2) ? (G - B + abs(A[p].x - A[p - 1].x)) : (abs(A[p].x - A[p - 1].x)));
while(head <= tail) {
if(que[tail].x >= A[p].y) {
num += que[tail].y;
tail--;
}
else break;
}
que[++tail].x = A[p].y;
que[tail].y = num;
}
cout << cost << endl;
}
signed main() {
init();
}
P1792
种树，超级经典的反悔贪心的说 qwq
一般来讲，让你求最大或小的 \(K\) 个，那么会用一个二叉堆维护。而且每次求出来堆顶后，会对堆顶进行一个“分裂”，扩展出其它的选择。比如这题。P2048 超级钢琴也是这样的一个思路 qwq。
首先考虑 \(K = 1\) 的情况，很显然我们会取最大的一个 \(A_i\)。
考虑完了这种情况，下面我们考虑 \(K = 2\)。除了取单个的一个 \(A_i\)，我们还可能会有什么操作呢？先不考虑环的一些细节，像酱紫
* * * i-1 i i+1 * * *
对于此时的决策，我们有三种可能
- \(A_1\sim A_{i - 2}\).
- \(A_{i+2}\sim A_n\)
- 选 \(A_{i - 1}, A_{i+1}\) 而不选 \(A_i\)。
注意第三种是有可能的，在不考虑环的情况下，比如是这样的序列
1 1 1 1 3 4 3 1 1 1
第一次我们会选 \(4\)，但是第二次只能选 \(1\)，这显然不如选它旁边的 \(3, 3\)。
第一个和第二个可能很好维护（之前已经在大根堆里面放过了），那么第三个怎么维护呢？由于我们已经做好了 \(A_i\) 的贡献，那么这个时候我们考虑退回 \(A_i\) 的贡献，也就是说把 \(A_{i - 1}+ A_{i+1} - A_i\) 放进大根堆里面。这相当于把 \(A_{i-1}, A_{i+1}, A_i\) 合并了。合并成了一个新元素。这很容易证明，我们只会这么搭配它们俩。
这样合并，那么我们的左边就可能不是 \(i-1\) 右边可能不是 \(i+1\)，因为合并过了，那么怎么办呢？我们可以记录 \(left_i\) 代表左边的，\(right_i\) 代表 \(i\) 右边的。环也很好通过 \(left\) 和 \(right\) 体现。\(vis_i\) 代表 \(i\) 有没有被合并过。每次都用大根堆取出堆顶 \(a_i\)，加入贡献，合并 \(a_i = a_{i-left}+ a_{i+right} - a_i\)，顺便修改三者的 \(left, right\)。特别注意注意，如果 \(i\) 被合并过了，那么我们就不会处理。这很好理解：用归纳法，如果我们前面做的一定是最优解，而且根据贪心的最优子结构，所以我这一步一定是在之前的步上才能走出来最优解。否则这题就不能贪心了。
更加严谨的证明我真的不会呜呜呜呜不会证反悔贪心的最优子结构，不过可以这样记：dp 和贪心的最优子结构使我们不用去额外考量之前所做的操作是否会影响到现在的操作，如果会，那么这道题就不能用 dp 和贪心
#include <iostream>
#include <queue>
#define MAXN 1000000
#define QWQ cout << "QWQ" << endl;
using namespace std;
int a[MAXN + 10];
int l[MAXN + 10], r[MAXN + 10];
struct node {
int id, val;
node(int I, int V) {
id = I, val = V;
}
bool operator < (const node &other) const {
return val < other.val;
}
};
bool vis[MAXN + 10];
int main() {
priority_queue <node> que;
int n, m; cin >> n >> m;
if(m * 2 > n) {
cout << "Error!" << endl;
return 0;
}
for(int p = 1; p <= n; p++) {
cin >> a[p];
int L, R;
if(p == 1) l[p] = n, r[p] = 2;
else if(p == n) l[p] = n - 1, r[p] = 1;
else l[p] = p - 1, r[p] = p + 1;
que.push(node(p, a[p]));
}
int ans = 0;
for(int p = 1; p <= m; p++) {
while(vis[que.top().id]) que.pop();
int qwq = que.top().id;
vis[l[qwq]] = 1, vis[r[qwq]] = 1;
ans += que.top().val;
a[qwq] = a[l[qwq]] + a[r[qwq]] - a[qwq];
que.push(node(qwq, a[qwq]));
que.pop();
l[qwq] = l[l[qwq]], r[qwq] = r[r[qwq]];
l[r[qwq]] = qwq, r[l[qwq]] = qwq;
}
cout << ans << endl;
}
顺便一提什么“双向链表模型”又是什么鬼哦，这道题双向链表只是为了方便叙述，本质上是维护左右的编号，这个模型属实是对着题目瞎讲了（雾
标签：int,long,反悔,que,贪心,我们,题单 From： https://www.cnblogs.com/thirty-two/p/17574539.html