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

lam_dyr · 2024-12-30 09:41:44 · 题解

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

题意

有一群孩子围成一个圈，每个孩子都有一个积分。你需要给每个孩子分发糖果，满足以下条件：

• 每个孩子至少要得到一颗糖果。
• 如果一个孩子的评分比他相邻的下一个孩子高，并且他的糖果数小于等于下一个孩子的糖果数，那么他的糖果数必须增加 1。
• 孩子是围成一个圈的，所以第一个孩子和最后一个孩子是相邻的。

求满足条件所需要的最小糖果数。

Solution

首先给每个孩子一人一块糖果，接着一直循环，每次遍历所有孩子。如果这个孩子的积分比下一个孩子的积分多，但糖相等或更少，则给这个孩子的糖果数量加一。每进行完一次循环更新一遍答案，如果这次和上次的答案一样就终止。

为什么这样做能使总糖果数最少呢？因为在每次遍历中我们只在最低条件下满足。

因为孩子是环形的，注意先特判首尾。

Code

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int n,a[N],ans[N],minn=1e9;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        ans[i]=1;
    }
    while(true){
        if(ans[1]<=ans[n] && a[1]>a[n]) ans[1]++;
        if(ans[n]<=ans[1] && a[n]>a[1]) ans[n]++;
        for(int i=1;i<=n;i++){
            if(ans[i]<=ans[i+1] && a[i]>a[i+1]) ans[i]++;
            if(ans[i]>=ans[i+1] && a[i]<a[i+1]) ans[i+1]++;
        }
        int res=0;
        for(int i=1;i<=n;++i) res+=ans[i];
        if(res==minn) break;
        minn=res;
    }
    cout<<minn;
    return 0;
}