记录编号	296906	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]种树	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	1.574 s
提交时间	2016-08-16 09:04:48	内存使用	2.46 MiB

#include <cstdio>
#include <set>
using namespace std;
const int maxn = 200010;
inline void read(int &x){
	x=0;char ch;bool flag = false;
	while(ch=getchar(),ch<'!');if( ch == '-' ) ch=getchar(),flag = true;
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');if( flag ) x=-x;
}
int n,m,a[maxn];
struct Node{
	int val,num;
};
typedef set<Node> ll;
bool operator < (const Node &a,const Node &b){
	return a.val == b.val ? a.num > b.num : a.val > b.val;
}
void del(ll &s,int* a,int num){
	if( num == 0 ) return;
	ll::iterator tmp = s.find( (Node){a[num],num} );
	if( tmp != s.end() ) s.erase(tmp);
}
int pre[maxn],suc[maxn];
int main(){
	freopen("nt2011_tree.in","r",stdin);
	freopen("nt2011_tree.out","w",stdout);
	read(n);read(m);
	for(int i=1;i<=n;++i) read(a[i]);
	if( m > (n >> 1) ){
		printf("Error!\n");
		//getchar();getchar();
		return 0;
	}else{
		int ans = 0;
		for(int i=1;i<=n;++i) pre[i] = i-1,suc[i] = i+1;
		pre[1] = n;suc[n] = 1;
		ll s;s.clear();
		for(int i=1;i<=n;++i) s.insert((Node){a[i],i} );
		Node tmp;
		for(int i=1;i<=m;++i){
			tmp = *s.begin();
			s.erase(s.begin());
			ans += tmp.val;
			del(s,a,pre[tmp.num]);
			del(s,a,suc[tmp.num]);
			a[tmp.num] = a[pre[tmp.num]] + a[suc[tmp.num]] - a[tmp.num];
			pre[tmp.num] = pre[pre[tmp.num]];
			suc[tmp.num] = suc[suc[tmp.num]];
			pre[suc[tmp.num]] = suc[pre[tmp.num]] = tmp.num;
			s.insert((Node){a[tmp.num],tmp.num});
		}
		printf("%d",ans);
	}
	//getchar();getchar();
	return 0;
}