【NOIP2017模拟】猫种花

题面-猫

  信息组最近猫成灾了!隔壁物理组也拿猫没办法.信息组组长只好去请神刀手来帮他们消灭猫.信息组现在共有n 只猫(n 为正整数),编号为1 到n,站成了一个环,第i 只猫的左边是第i-1 只猫,右边是第i+1 只猫.特别的,第1 只猫的左边是第n 只猫,第n 只猫的右边是第1 只猫.每只猫拥有价值,表示消灭它能给信息组组长带来的声誉.注意,有的猫价值为负数,这意味着消灭它会损害组长的声誉.神刀手可以选择一些猫消灭掉.但是,我们的组长实际上非常喜欢猫,他希望神刀手不要消灭两只相邻的猫.
  神刀手的能力组长现在还不知道.所以,组长希望知道对于所有的1<=m<=n/2,如果神刀手刚好消灭m 只猫,他最多能获得的声誉.信息组组长当然知道怎么做啦！但是他想考考你……

题面-种花

  经过三十多个小时的长途跋涉，小Z和小D终于到了NOI现场——南山南中学。一进校园，小D就被花所吸引了（不要问我为什么），遍和一旁的种花园丁交（J）流（L）了起来。
  他发现花的摆放竟有如此奥秘：圆形广场共有 N 个种花的位置，顺时针编号1到N。并且每个位置都有一个美观度ai ，如果在这里种花就可以得到这ai 的美观度。但由于地处南山土壤肥力欠佳，两株花不能种在相邻的位置（1号和N号也算相邻位置）。校方一共给了 M 株花，经过园丁的精妙摆放，才能如此吸引小D。所以现在小D也想知道摆这 N 株花可以得到的最大美观度。

解法

贪心：
  其实一开始我的想法是DP，但是发现太难搞了，所以换了一个思路，发现可以贪心来做。
  之前考NOIP模拟赛时做过一道题，题面是：

  这三道题都很类似，都是使用贪心解决，也都是有一个“反悔”的操作（堆模拟网络流？）
  具体做法是这样的：我们用一个大根堆，每一次取出堆顶元素$i$，将其贡献（$A_i$）加入答案，然后给其左右的元素打上标记（事先预处理好左右相邻的），然后将其左右元素的A加在$i$上并减去$A_i$，然后将$i$再丢入堆中，这样的话下一次再选到它，就说明选左右比选中间更优，加上答案之后就会把$A_i$抵掉

复杂度

O（$mlogn$）

代码

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#define Rint register int
#define Lint long long int
using namespace std;
const int N=200010;
struct task
{int x,w;bool operator < (const task &a) const{return w<a.w;}
}A;
bool vis[N];
int w[N],l[N],r[N];
int n,m,ans;
priority_queue<task> q;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%d",&w[i]);q.push( (task){ i,w[i] } );}if( 1+(n-1)/2<m )   { printf("Error!");return 0; }for(int i=1;i<=n;i++)   l[i]=i-1,r[i]=i+1;l[1]=n,r[n]=1;for(int i=1;i<=m;i++){A=q.top(),q.pop();while( vis[A.x] )   A=q.top(),q.pop();ans+=A.w;w[A.x]=w[l[A.x]]+w[r[A.x]]-A.w;//相等于是一次反悔的机会（可以不用A.x,而使用l和r,这样的话计算因为之前有一个w[A.x],所以和这里的-w[A.x]抵消,得到w[l]+w[r]）vis[l[A.x]]=vis[r[A.x]]=1;l[A.x]=l[l[A.x]],r[A.x]=r[r[A.x]];r[l[A.x]]=A.x,l[r[A.x]]=A.x;q.push( (task){ A.x,w[A.x] } );}printf("%d\n",ans);return 0;
}