记录编号	142677	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]种树	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.029 s
提交时间	2014-12-10 10:23:59	内存使用	2.60 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<set>
using namespace std;
const int SIZEN=200010,INF=0x7fffffff/2;
class Position{//一个位置
public:
	int dlt;//带来的增量
	int id;//编号
	void print(void){printf("(%d %d)",dlt,id);}
};
void print(Position p){p.print();}
bool operator < (Position a,Position b){
	if(a.dlt==b.dlt) return a.id>b.id;
	return a.dlt>b.dlt;
}
void erase_position(set<Position> &S,int A[],int k){
	if(!k) return;
	set<Position>::iterator key=S.find((Position){A[k],k});
	if(key!=S.end()) S.erase(key);
}
int test(int A[],int N,int M){//A[1]~A[N]选M个
	A[0]=0;
	static int pre[SIZEN],nxt[SIZEN];
	memset(pre,0,sizeof(pre));
	memset(nxt,0,sizeof(nxt));
	for(int i=1;i<N;i++){
		nxt[i]=i+1;
		pre[i+1]=i;
	}
	nxt[N]=1;pre[1]=N;
	static set<Position> S;
	S.clear();
	int ans=0;
	for(int i=1;i<=N;i++) S.insert((Position){A[i],i});
	for(int i=1;i<=M;i++){
		Position now=*S.begin();S.erase(S.begin());
		ans+=now.dlt;
		erase_position(S,A,pre[now.id]);
		erase_position(S,A,nxt[now.id]);
		A[now.id]=A[pre[now.id]]+A[nxt[now.id]]-A[now.id];
		pre[now.id]=pre[pre[now.id]];
		nxt[now.id]=nxt[nxt[now.id]];
		nxt[pre[now.id]]=pre[nxt[now.id]]=now.id;
		S.insert((Position){A[now.id],now.id});
	}
	return ans;
}
int N,M;
int A[SIZEN]={0};
void work(void){
	if(M*2>N){
		printf("Error!\n");
		return;
	}
	printf("%d\n",test(A,N,M));
}
void read(void){
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++) scanf("%d",&A[i]);
}
int main(){
	freopen("nt2011_tree.in","r",stdin);
	freopen("nt2011_tree.out","w",stdout);
	read();
	work();
	return 0;
}