P3584 [POI2015] LAS

zac2010 · 2023-09-22 14:30:22 · 题解

注：为了方便叙述，在下文中，我们用 \text{next}(i) 表示第 i 个人右边的食物，\text{pre}(i) 表示第 i 个人左边的食物。

看到题目时一个直观的想法：对于所有 c_{\text{pre}(i)}\geq c_{\text{next(i)}}\times 2 或者 c_{\text{next}(i)}\geq c_{\text{pre}(i)}\times 2 的人，他必定是取左右两边较大的食物的。

考虑把确定上述那些人的选择。具体的，我们把这些人选择的食物热量给去掉一半。之后，可能会出现新的满足条件的人。故而我们采用一个广搜的思想，把新的人也给加入一个队列进行拓展。

最后我们还会剩下一个环，其中环上任意节点满足：要不是他已经选择过食物了，就是他左右两边的食物不满足上述条件。直接对每个位置进行贪心取就行了：c_{\text{pre}(i)} 和 c_{\text{next}(i)} 哪个大取哪个。贪心正确性显然。

为了防止出现浮点数，我在代码中把每个 c_i 都乘上了 2。易发现这样不影响答案。

#include <bits/stdc++.h>
#define FL(i, a, b) for(int i = (a); i <= (b); i++)
#define FR(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 1e6 + 10;
int n, a[N], b[N], ans[N];
queue<pair<int, int> > q;
int pre(int i){return (i - 1 + n) % n;}
int nxt(int i){return (i + 1) % n;}
void psh(int i){
    if(!~ans[i] && b[i] >= b[nxt(i)] * 2ll){
        q.emplace(i, i);
        b[ans[i] = i] -= a[i];
    }
    if(!~ans[i] && b[nxt(i)] >= b[i] * 2ll){
        q.emplace(i, nxt(i)), b[ans[i] = nxt(i)] -= a[nxt(i)];
    }
}
int main(){
    scanf("%d", &n);
    fill(ans, ans + n, -1);
    FL(i, 0, n - 1){
        scanf("%d", &a[i]);
        b[i] = a[i] << 1;
    }
    FL(i, 0, n - 1) psh(i);
    while(!q.empty()){
        auto u = q.front(); q.pop();
        psh(pre(u.second)), psh(u.second);
    }
    FL(i, 0, n - 1){
        if(~ans[i]) printf("%d ", ans[i] + 1);
        else{
            if(b[i] > b[nxt(i)])
                printf("%d ", i + 1), b[i] -= a[i];
            else printf("%d ", nxt(i) + 1), b[nxt(i)] -= a[nxt(i)];
        }
    }
    return 0;
}