【NOIP2017提高A组模拟9.17】猫

题目

信息组最近猫成灾了!

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

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

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

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

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

但是他想考考你……

从cat.in 中读入

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

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

输出到文件cat.out

输出共n/2 行,

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

输入1：

8

1 1 8 1 1 9 1 1

输入2：

11

5 6 7 8 9 10 9 8 7 6 5

输出1：

9

17

18

12

输出2：

10

18

26

32

38

对于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;
}