P3584 [POI2015]LAS

POI 合集。

第一个想法是若出现相邻的两个食物 $(x,y)$ 满足 $2a_x<a_y$ 或 $2a_y<a_x$，说明能够选择食物 $x,y$ 的人一定会选择 $a$ 值较大的那一个，因为就算有人和他抢食物他也能吃到热量较高的那个。

可能出现钦定一个人在 $x,y$ 之间选择 $y$ 后 $y,z$ 又出现了一个数大于另一个数的两倍的情况，所以用队列进行 “松弛”。

松弛完毕后，对于没有钦定食物的所有人贪心地选择他相邻两个食物中热量较高的那个即可。若 $x$ 选了食物 $x+1$，那么 $x+1$ 就一定不会选食物 $x+1$，因为 $\dfrac{a_{x+1}}{2}\leq a_{x+2}$。故两个没有钦定食物的人不可能选到同一食物，所以每个人的决策互不干扰，贪心正确性得以保证。

为防止出现小数的情况，可以在一开始将所有食物热量乘以 $2$。注意此时判断 $2a_x<a_y$ 需要开 long long。时间复杂度线性。

const int N = 1e6 + 5;
int n, q[N << 1], res[N], hd = 1, tl; ll c[N];
int check(int p) {
	if(res[p]) return -1;
	int pre = p, suf = p % n + 1;
	if(c[pre] << 1 < c[suf]) return suf;
	if(c[suf] << 1 < c[pre]) return pre;
	return -1;
}

int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) c[i] = read() << 1;
	for(int i = 1; i <= n; i++) {
		int p = check(i);
		if(p != -1) q[++tl] = i;
	} while(hd <= tl) {
		int t = q[hd++], p = check(t);
		if(p == -1) continue;
		res[t] = p, c[p] >>= 1;
		if(check(p)) q[++tl] = p;
		if(check(p == 1 ? n : p - 1)) q[++tl] = p == 1 ? n : p - 1;
	}
	for(int i = 1; i <= n; i++) if(!res[i]) {
		int pre = i, suf = i % n + 1;
		if(c[pre] > c[suf]) res[i] = pre, c[pre] >>= 1;
		else res[i] = suf, c[suf] >>= 1;
	}
	for(int i = 1; i <= n; i++) print(res[i]), pc(' '); 
	return cerr << "Time : " << clock() << " ms" << endl, flush(), 0;
}