东方幻想乡系列模拟赛-取数

发布于 2017-08-19  113 次阅读


#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
int vis[400005];
struct s
{
	int l,r,w;
}s[400005];
int main()
{
	freopen("choose.in","r",stdin);
	freopen("choose.out","w",stdout);
	int n,m;
	scanf(
	if( m>(n/2) )
	{
		printf("Error!");
		return 0;
	}
	priority_queue< pair<int,int> >q;
	for(int i=1;i<=n;i++)
	{
		scanf(
		s[i].l=i-1;
		s[i].r=i+1;
		q.push(make_pair(s[i].w,i));
	}
	s[1].l=n;
	s[n].r=1;
	int ans=0;
	for(int k=1;k<=m;k++)
	{
		int i=q.top().second;
		q.pop();
		if(vis[i]!=0)
		{
			k--;
			continue;
		}
		ans+=s[i].w;
			s[++n].w=s[s[i].l].w+s[s[i].r].w-s[i].w;
			vis[s[i].l]=vis[s[i].r]=vis[i]=1;
			s[n].l=s[s[i].l].l;
			s[n].r=s[s[i].r].r;
			s[s[s[i].l].l].r=n;
			s[s[s[i].r].r].l=n;
		q.push(make_pair(s[n].w,n));
	}
	cout<<ans;
}

return 0是不可能的,这辈子都不可能return 0