反悔型贪心好例题——CF1271D Portals
Sweetlemon
2019-12-18 09:57:44
### CF1271D Portals
这是一道有非常多做法的题目，值得一做。
#### 基础贪心思想
一个比较重要的贪心思想是，对于每一个城堡，我们都尽可能在最晚的时间控制，也就是早控制不如晚控制。这一点很容易理解，因为如果早控制，士兵到了城堡也是闲着，不如留在军队里凑数，到了时间再前往目标城堡。
因此，我们可以记录每一个城堡的最晚控制时间，在最晚控制时间才派出士兵控制。
#### 动态规划算法
看到这题的数据范围居然只有 $5000$，那就一定可以动态规划了。
设 $f[i][j]$ 表示攻下了前 $i$ 个城堡且手上还剩 $j$ 个士兵时，被控制的最大总价值。那么这个问题就类似一个背包，直接转移一下就可以得到答案了。只要注意边界——打第 $i$ 个城堡前手上必须有至少 $a[i]$ 个士兵。
时间复杂度 $O(n^2)$ 量级。
```cpp
#include <cstdio>
#include <cctype>
#include <vector>
#include <functional>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x)\
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout);
#define LOWBIT(x) ((x)&(-(x)))
#define MAXN 5005
#define INF 19260817
using namespace std;
typedef long double ld;
typedef long long ll;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void); //快读，实现略去
void ayano(io_t x,char spliter='\n'); //快写，实现略去
int n;
int a[MAXN],b[MAXN],c[MAXN];
int f[MAXN][MAXN];
int tcont[MAXN]; //每个城堡控制的最晚时间
pair<int,int> prs[MAXN]; //把可控制的城堡和它的价值放在 pair 中
int main(void){
int m,k;
n=seto(),m=seto(),k=seto();
for (int i=1;i<=n;i++)
a[i]=seto(),b[i]=seto(),c[i]=seto(),tcont[i]=i;
while (m--){
int u,v;
u=seto(),v=seto();
tcont[v]=max(tcont[v],u);
}
for (int i=1;i<=n;i++)
prs[i]=make_pair(tcont[i],c[i]);
sort(prs+1,prs+n+1);
for (int t=0;t<=k;t++)
f[0][t]=0;
for (int t=k+1;t<=5000;t++)
f[0][t]=-INF;
int tpoint=1; //当前可控制的城堡指针
for (int i=1;i<=n;i++){
for (int t=0;t<=5000;t++)
f[i][t]=-INF;
for (int t=a[i];t<=5000;t++)
f[i][t+b[i]]=max(f[i][t+b[i]],f[i-1][t]);
while (tpoint<=n && prs[tpoint].first==i){
for (int t=0;t<5000;t++)
f[i][t]=max(f[i][t],f[i][t+1]+prs[tpoint].second);
tpoint++;
}
}
int ans=-1;
for (int t=0;t<=5000;t++)
ans=max(ans,f[n][t]);
ayano(ans);
return 0;
}
```
#### 数据结构优化贪心算法
我们可以想到一个这样的贪心：先不控制任何一个城堡，完成游戏后再按照价值从大到小的顺序尽可能地控制城堡。
这个贪心为什么是正确的呢？主要原因还是，控制任何一个城堡需要的士兵都是 $1$ 人。如果留着这个价值较大的城堡不控制，对后续的影响最多也就是“能多控制一个价值较小的城堡”，这一定是不划算的。
那么如何判断“能否控制这个城堡”呢？
考虑控制这个城堡对后续的影响——控制了这个城堡，今后攻打城堡时可用的士兵就会少一人。因此我们可以用一个数组记录“攻打这个城堡时，可用士兵比必需士兵（$a[i]$）多多少”。假设我们想要在 $t$ 时刻控制一个城堡，那么 $t$ 时刻以后的可用士兵就会少一人，我们就要检查，$t$ 时刻以后的“盈余士兵”是否都大于 $0$。如果确实大于 $0$，表示我们可以控制这个城堡，我们就需要更新“盈余士兵”——$t$ 时刻以后的盈余士兵都少一人。
区间减和区间最小值，可以方便地用线段树实现。
时间复杂度 $O(n\log n)$ 量级。
```cpp
#include <cstdio>
#include <cctype>
#include <vector>
#include <functional>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x)\
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout);
#define LOWBIT(x) ((x)&(-(x)))
#define MAXN 5005
#define MAX4N 20005
#define INF 19260817
using namespace std;
typedef long double ld;
typedef long long ll;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void);
void ayano(io_t x,char spliter='\n');
struct Ene{
int l,r,val,addv;
#define L(x) ((stree[(x)]).l)
#define R(x) ((stree[(x)]).r)
#define X(x) ((stree[(x)]).val)
#define ADD(x) ((stree[(x)]).addv)
#define LC(x) (((x)<<1))
#define RC(x) (((x)<<1)^1)
};
int n;
int a[MAXN],b[MAXN],c[MAXN];
int rst[MAXN];
int tcont[MAXN];
pair<int,int> prs[MAXN];
Ene stree[MAX4N];
void build_tree(int root,int l,int r);
void add(int root,int l,int r,int v);
int query(int root,int l,int r);
void pushdown(int root);
int main(void){
int m,k;
n=seto(),m=seto(),k=seto();
for (int i=1;i<=n;i++)
a[i]=seto(),b[i]=seto(),c[i]=seto(),tcont[i]=i;
while (m--){
int u,v;
u=seto(),v=seto();
tcont[v]=max(tcont[v],u);
}
for (int i=1;i<=n;i++)
prs[i]=make_pair(c[i],tcont[i]);
sort(prs+1,prs+n+1);
for (int i=1;i<=n;i++){
if (k<a[i]){
ayano(-1);
return 0;
}
rst[i-1]=k-a[i];
k+=b[i];
}
rst[n]=k;
int troot=1;
build_tree(troot,1,n);
ll ans=0;
for (int i=n;i;i--){
int ucont=prs[i].second;
int tw=prs[i].first;
if (query(troot,ucont,n)>0)
add(troot,ucont,n,-1),ans+=tw;
}
ayano(ans);
return 0;
}
void build_tree(int root,int l,int r){
L(root)=l,R(root)=r,ADD(root)=0;
if (l==r){
X(root)=rst[l];
return;
}
int mid=(L(root)+R(root))>>1;
build_tree(LC(root),l,mid);
build_tree(RC(root),mid+1,r);
X(root)=min(X(LC(root)),X(RC(root)));
}
void add(int root,int l,int r,int v){
if (l<=L(root) && r>=R(root)){
X(root)+=v,ADD(root)+=v;
return;
}
pushdown(root);
int mid=(L(root)+R(root))>>1;
(l<=mid)?(add(LC(root),l,r,v)):(void());
(r> mid)?(add(RC(root),l,r,v)):(void());
X(root)=min(X(LC(root)),X(RC(root)));
}
int query(int root,int l,int r){
if (l<=L(root) && r>=R(root))
return X(root);
pushdown(root);
int mid=(L(root)+R(root))>>1;
int ans=INF;
(l<=mid)?(ans=min(ans,query(LC(root),l,r))):(0);
(r> mid)?(ans=min(ans,query(RC(root),l,r))):(0);
return ans;
}
void pushdown(int root){
int tadd=ADD(root);
ADD(root)=0;
if ((!tadd) || (L(root)==R(root)))
return;
ADD(LC(root))+=tadd,X(LC(root))+=tadd;
ADD(RC(root))+=tadd,X(RC(root))+=tadd;
}
//略去读入输出优化的实现
```
#### 反悔型贪心
事实上，这题还有非常容易实现的反悔型贪心做法。
反悔型贪心同样基于“控制任何一个城堡需要的士兵都是 $1$ 人”的条件。它的思路是：在每个城堡的“最晚控制点”，先贪心地把城堡控制了。
这样就会存在问题：后面士兵可能就不够了，游戏失败了啊。那我们就会后悔，“要是那时没有控制某一个城堡就好了”；而程序可以实现“时光倒流”，把当时的操作反悔掉，也就是减少 $c[i]$ 个重要点数，增加一名士兵。贪心地想，因为每一个城堡都是贡献 $1$ 名士兵，所以我们肯定会选择反悔“最不重要”的、也就是 $c[i]$ 最小的城堡。
于是，我们只需要在控制城堡的时候，把城堡放进一个堆里，每次需要反悔时取堆中最不重要的城堡进行反悔即可；如果需要反悔时堆已经为空，就说明这个游戏不可能完成，输出 $-1$ 即可。
注意一个易错点：游戏结束时，如果士兵人数是负值，自然是不可行的。因此最后如果人数为负，则还要进行反悔。
时间复杂度 $O(n\log n)$ 量级。
这道题体现了反悔型贪心的基本思路（之一），非常适合作为反悔贪心的入门例题。
类似的反悔型贪心还有这道题：[SP348 EXPEDI - Expedition](https://www.luogu.com.cn/problem/SP348)，可以作为例题的配套练习。它们有一个共同特点，那就是都有一个维度是 $1$——每个城堡所需士兵都是 $1$ 人；每个加油站对答案的贡献都是 $1$——这也许是这类反悔型贪心成立的条件。
下面是本题代码。
奇怪的是，dp 的代码只用时 $109 \text{ms}$，线段树的代码用时 $156 \text{ms}$，堆的代码用时竟达到 $171 \text{ms}$！理论上快的代码实际上反而慢，确实有些奇怪。
```cpp
#include <cstdio>
#include <cctype>
#include <functional>
#include <algorithm>
#define MAXIOLG 25
#define FILENAME(x)\
freopen(x".in","r",stdin);\
freopen(x".out","w",stdout);
#define LOWBIT(x) ((x)&(-(x)))
#define MAXN 5005
using namespace std;
typedef long double ld;
typedef long long ll;
typedef ll io_t;
io_t shin[MAXIOLG];
io_t seto(void);
void ayano(io_t x,char spliter='\n');
int n;
int a[MAXN],b[MAXN],c[MAXN];
int rst[MAXN];
int tcont[MAXN];
pair<int,int> prs[MAXN];
int que[MAXN];
int main(void){
int m,k;
n=seto(),m=seto(),k=seto();
for (int i=1;i<=n;i++)
a[i]=seto(),b[i]=seto(),c[i]=seto(),tcont[i]=i;
while (m--){
int u,v;
u=seto(),v=seto();
tcont[v]=max(tcont[v],u);
}
for (int i=1;i<=n;i++)
prs[i]=make_pair(tcont[i],c[i]);
sort(prs+1,prs+n+1);
int qtail=0,tpoint=1;
ll ans=0;
for (int i=1;i<=n;i++){
while (k<a[i] && qtail){
k++;
ans+=que[0];
pop_heap(que,que+qtail);
qtail--;
}
if (k<a[i]){
ayano(-1);
return 0;
}
k+=b[i];
while (tpoint<=n && prs[tpoint].first==i){
k--,ans+=prs[tpoint].second;
que[qtail++]=-prs[tpoint].second;
push_heap(que,que+qtail);
tpoint++;
}
}
while (k<0 && qtail){
k++;
ans+=que[0];
pop_heap(que,que+qtail);
qtail--;
}
ayano(ans);
return 0;
}
//略去读入输出优化的实现
```