自动搬运

查看原文

来自洛谷，原作者为

	zac2010 a vegedog

搬运于2025-08-24 21:50:26，当前版本为作者最后更新于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;
}