题解：B4091 [CSP-X2020 山东] 分糖果

SkyLines · 2024-12-24 20:16:19 · 题解

Solution

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

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

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

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

不难证明，不会出现 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;
}