注：为了方便叙述，在下文中，我们用 \(\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;
}