自动搬运

查看原文

来自洛谷，原作者为

	SkyLines Everything is nothing without you. You make it happen.

搬运于2025-08-24 21:17:00，当前版本为作者最后更新于2024-12-24 20:16:19，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

首先，给所有孩子 $1$ 个糖果。

然后，调整若干次。对于每一次调整 $i,j$（$j$ 为 $i$ 后一个人）而言，当前不公平的有两种情况：

• $i$ 的表现评分比 $j$ 小，且 $i$ 的糖果大于等于 $j$。

• $i$ 的表现评分比 $j$ 大，且 $j$ 的糖果大于等于 $i$。

显然，要使糖果总数最小，两种情况的调整分别如下：

• $j$ 的糖果比 $i$ 多 $1$ 个。

• $i$ 的糖果比 $j$ 多 $1$ 个。

最后，将所有孩子得到的糖果相加即为答案。

不难证明，不会出现 $a_1<a_2< \dots <a_n<a_1$ 的情况，即不会无限循环。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e5 + 5;
int n, a[N], cnt[N], j, ans;
bool flg;
signed main(){
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++){
		scanf("%lld", &a[i]);
		cnt[i] = 1;
	}
	while(1){
		flg = 0;
		for(int i = 1; i <= n; i++){
			j = ((i == n) ? 1 : (i + 1));
			if(a[i] < a[j] && cnt[i] >= cnt[j]){
				cnt[j] = cnt[i] + 1;
				flg = 1;
			}else if(a[i] > a[j] && cnt[j] >= cnt[i]){
				cnt[i] = cnt[j] + 1;
				flg = 1;
			}
		}
		if(!flg) break;
	}
	for(int i = 1; i <= n; i++) ans += cnt[i];
	printf("%lld", ans);
	return 0;
}