RT，简单反悔贪心

#include <bits/stdc++.h>
using namespace std;
#define M 1000010
#define int long long
int n,m,cnt,ans,x,y,cntp;
int a[M];
struct node
{
	int l,r,v;
}t[M];
struct cmp
{
	bool operator()(int XX,int YY)
	{
		return (t[XX].v==t[YY].v?XX<YY:t[XX].v>t[YY].v);
	}
};
priority_queue<int,vector<int>,cmp>q,qd;
signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		y=x;
		cin>>x;
		a[i-1]=x-y;
	}
	n--;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		t[i].l=i-1;
		t[i].r=(i+1)%(n+1);
		t[i].v=a[i];
		q.push(i);
	}
	cntp=n;
	while(cnt<m)
	{
		while(!qd.empty()&&q.top()==qd.top())
		{
			q.pop();qd.pop();
		}
		cnt++;x=q.top();q.pop();
		if(t[x].l) qd.push(t[x].l);
		if(t[x].r) qd.push(t[x].r);
		ans+=t[x].v;
		y=(t[t[x].l].v+t[t[x].r].v)-t[x].v;
		if(t[x].r&&t[x].l)
		{
			++cntp;
			t[t[t[x].l].l].r=cntp; t[0].r=0;
			t[t[t[x].r].r].l=cntp; t[0].l=0;
			t[cntp].l=t[t[x].l].l;
			t[cntp].r=t[t[x].r].r;
			t[cntp].v=y;q.push(cntp);
		}
		else
		{
			if(!t[x].r) t[t[x].l].r=0;
			if(!t[x].l) t[t[x].r].l=0;
		}
	}
	cout<<ans<<endl;
	return 0;
}