种树反悔操作【贪心】

本人水平有限，题解不到为处，请多多谅解

本蒟蒻谢谢大家观看

具体的解析大佬博客里有

推荐：博客

我这里是来讲下如何代码实现的

我们用pair来实现堆优化，first代表权值，second代表权值位置

1 void del(int x){
2     pre[nxt[x]]=pre[x];
3     nxt[pre[x]]=nxt[x];
4     flag[x]=true;
5 }

以上代码如何理解呢？

先看一幅图：

我们先算4个点

如果依照最基本的贪心策略（即取最大值）

应该是这样：

但是我们发现这并不是最优解，ans==10，明显小于 ans==16

这时就要进行反悔操作，即赎买，算差值

记录我们取的当前节点的最大值与其左右两个节点之和的差值 (来方便赎买) 即反悔操作

可知：差值为7 (8+8-9=7)

这时我们把7放到原先9的位置上

我们发现8在我们取9的时候被打上了标记，不能取

即：

1 flag[x]=true;

对于不能取的点，我们要让其退出堆内，即：

1 while (flag[Q.top().second]){
2         Q.pop();
3     }

这时堆里的最大值为7，就取出7来更新ans

1 pre[nxt[x]]=pre[x];
2     nxt[pre[x]]=nxt[x];

所以这两句话的意思是：

如果当m的两倍大于n的话，显然是无法种完m的（隔板插空），所以直接输出 Error!

code:

 1 #include<bits/stdc++.h>
 2 #pragma GCC optimize(3)
 3 #define int long long
 4 const int N=1e6+10;
 5 using namespace std;
 6 bool flag[N];
 7 int n,m,ans,node[N],pre[N],nxt[N];
 8 priority_queue<pair<int,int> > Q;
 9 inline int read(){
10     int x=0,f=1;char ch=getchar();
11     while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
12     while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
13     return x*f;
14 }
15 void del(int x){
16     pre[nxt[x]]=pre[x];
17     nxt[pre[x]]=nxt[x];
18     flag[x]=true;
19 }
20 void greedy(){
21     while (flag[Q.top().second]){
22         Q.pop();
23     }
24     int a=Q.top().second;
25     Q.pop();
26     ans+=node[a];
27     node[a]=node[nxt[a]]+node[pre[a]]-node[a];
28     del(pre[a]);
29     del(nxt[a]);
30     Q.push(make_pair(node[a],a));
31 }
32 signed main()
33 {
34     n=read(),m=read();
35     for (int i=1;i<=n;i++){
36         node[i]=read();
37         pre[i]=i-1;
38         nxt[i]=i+1;
39         Q.push(make_pair(node[i],i));
40     }
41     pre[1]=n;
42     nxt[n]=1;
43     if (m*2>n){
44         printf("Error!");
45         return 0;
46     }
47     for(int i=1;i<=m;i++){
48         greedy();
49     }
50     printf("%lld",ans);
51     return 0;
52 }

种树 反悔操作 【贪心】

种树反悔操作【贪心】