洛谷P1484：种树（反悔贪心）

洛谷P1484：种树（反悔贪心） 解析

反悔贪心好题。
我放弃wqs二分做法好吧。

要加强从边界和特殊情况入手思考问题的思想。

考虑选一个的时候，肯定是选最大值。
此时它两侧的值就不能选了。
那如果我后来不选这个最大值了，必然是我转而把它两侧的值都给选了，额外消耗一次代价，多获得了 a i − 1 + a i + 1 − a i a_{i-1}+a_{i+1}-a_i ai−1​+ai+1​−ai​ 的价值。
那么其实也就等价于我在选最大值的时候，把它和它两侧的元素等价成了一个 a i − 1 + a i + 1 − a i a_{i-1}+a_{i+1}-a_i ai−1​+ai+1​−ai​ 的元素。

维护一个链表即可。

#include
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OKn")
inline ll read(){
	ll x(0),f(1);char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int N=1e6+100;
const int M=1e6+100;
const int mod=1e9;

int n,m,s,k;

int l[N],r[N],val[N];
struct node{
	int val,id;
	bool operator < (const node o)const{return valq;
bool vis[N];
ll ans;
inline void del(int x){
	r[l[x]]=r[x];l[r[x]]=l[x];
	return;
}
signed main(){
	#ifndef ONLINE_JUDGE
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	#endif
	n=read();m=read();
	for(int i=1;i<=n;i++){
		l[i]=i-1;r[i]=i+1;
		val[i]=read();
		q.push((node){val[i],i});
	}
	l[n+1]=n;r[0]=1;
	
	while(q.top().val>0&&m){
		node o=q.top();q.pop();
		if(vis[o.id]) continue;
		m--;ans+=o.val;
		int x=o.id,ls=l[x],rs=r[x];
		int w=-o.val;
		if(ls) w+=val[ls];
		if(rs<=n) w+=val[rs];
		val[x]=w;
		vis[ls]=vis[rs]=1;
		if(ls) del(ls);
		if(rs<=n) del(rs);
		q.push((node){w,x});
	}
	printf("%lldn",ans);
	return 0;
}