【NOIP2017提高A组模拟9.17】猫

【NOIP2017 提高A组模拟9.17】猫

题目

Description

信息组最近猫成灾了!

隔壁物理组也拿猫没办法.

信息组组长只好去请神刀手来帮他们消灭猫.信息组现在共有n 只猫(n 为正整数),编号为1 到n,站成了一个环,第i 只猫的左边是第i-1 只猫,右边是第i+1 只猫.特别的,第1 只猫的左边是第n 只猫,第n 只猫的右边是第1 只猫.每只猫拥有价值,表示消灭它能给信息组组长带来的声誉.

注意,有的猫价值为负数,这意味着消灭它会损害组长的声誉.神刀手可以选择一些猫消灭掉.但是,我们的组长实际上非常喜欢猫,他希望神刀手不要消灭两只相邻的猫.

神刀手的能力组长现在还不知道.所以,组长希望知道对于所有的1<=m<=n/2,如果神刀手刚好消灭m 只猫,他最多能获得的声誉.

信息组组长当然知道怎么做啦！

但是他想考考你……

Input

从cat.in 中读入

数据第一行包括一个正整数n

第二行为n 个整数,依次代表第1,2,...,n 只猫的价值.

Output

输出到文件cat.out

输出共n/2 行,

第i 行表示假如神刀手刚好消灭i 只猫,信息组组长最多能获得的收益.

Sample Input

输入1：

1 1 8 1 1 9 1 1

输入2：

5 6 7 8 9 10 9 8 7 6 5

Sample Output

输出1：

输出2：

Data Constraint

对于30%的数据,满足n<=20

对于60%的数据,满足n<=2000

对于另外20%的数据,满足n 为偶数

对于100%的数据,满足1<=n<=200000,|每只猫的价值|<=1e9

题解

考虑一种最简单的贪心：每次选取最大的，删去两边的。但是这种方法会有一定的问题，例如当两边之和大于中间的就会出错。那么设想给程序一个反悔的机会，可以尝试将左右两边的猫缩成一只价值是两边减去中间的猫，那么如果下次选的是这只猫，就相当于选了两边的猫

用堆加上链表，堆可以用自带的优先队列

Code

#include<queue>

#include<cstdio>

#include<iostream>

#define ll long long

using namespace std;

struct node

{

	ll id,val;

};

bool operator < (const node &a,const node &b) {return a.val<b.val;}

priority_queue <node> q;

ll n,num,ans,a[400001],last[400001],next[400001];

bool b[400001];

int read()

{

	int res=0,fh=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') fh=-1,ch=getchar();

	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch-'0'),ch=getchar();

	return res*fh;

}

int main()

{

	freopen("cat.in","r",stdin);

	freopen("cat.out","w",stdout);

	n=read();

	for (int i=1;i<=n;++i)

	{

		a[i]=read();

		last[i]=i-1;next[i]=i+1;

		if (i==1) last[i]=n;

		if (i==n) next[i]=1;

		node x;

		x.id=i;x.val=a[i];

		q.push(x);

	}

	num=n;

	node mx;

	for (int i=1;i<=(n>>1);++i)

	{

		mx=q.top();

		q.pop();

		while (!q.empty()&&b[mx.id])

		{

			mx=q.top();

			q.pop();

		}

		ans+=mx.val;

		b[mx.id]=b[last[mx.id]]=b[next[mx.id]]=true;

		a[++num]=a[last[mx.id]]+a[next[mx.id]]-a[mx.id];

		next[num]=next[next[mx.id]];

		last[next[num]]=num;

		last[num]=last[last[mx.id]];

		next[last[num]]=num;

		node x;

		x.id=num;x.val=a[num];

		q.push(x);

		printf("%lld\n",ans);

	}

	fclose(stdin);

	fclose(stdout);

	return 0;

}