题目大意

对于 \(m = [1,\lfloor \frac n 2 \rfloor]\)

要求在一个序列中恰好选出 \(m\) 个不相邻的数使得权值和最大

其中 \(1\) 的左边是 \(n\)，\(n\) 的右边是 \(1\)

分析

比较经典的贪心

做法

链表记录一个点的前驱后继

然后每次选权值最大的点加入答案，把与它相邻的点标记

然后把它和与它相邻的点缩成一个点，权值为相邻点的权值和减去当前点的权值，加入大根堆

题解

\(Code\)

#include<cstdio>
#include<queue>
#define LL long long
using namespace std;

const int N = 4e5 + 5;
int n , nxt[N] , pre[N] , vis[N];
LL a[N];

struct node{
    int id; LL v;
    bool operator < (node c) const {return v < c.v;}
};
priority_queue<node> Q;

int main()
{
    freopen("cat.in" , "r" , stdin);
    freopen("cat.out" , "w" , stdout);
    scanf("%d" , &n);
    for(register int i = 1; i <= n; i++)
    {
        scanf("%lld" , &a[i]);
        nxt[i] = (i == n ? 1 : i + 1) , pre[i] = (i == 1 ? n : i - 1);
        Q.push(node{i , a[i]});
    }
    node now; LL ans = 0; int m = n / 2;
    while (m--)
    {
        now = Q.top() , Q.pop();
        while (!Q.empty() && vis[now.id]) now = Q.top() , Q.pop();
        ans += now.v , printf("%lld\n" , ans);
        vis[now.id] = vis[nxt[now.id]] = vis[pre[now.id]] = 1;
        a[++n] = a[nxt[now.id]] + a[pre[now.id]] - a[now.id];
        nxt[n] = nxt[nxt[now.id]] , pre[n] = pre[pre[now.id]];
        nxt[pre[n]] = pre[nxt[n]] = n;
        Q.push(node{n , a[n]});
    }
}