题解：B4091 [CSP-X2020 山东] 分糖果
yyycj
·
·
题解
题目简述
求所有孩子糖果数总和的最小值。
## 主要思路
首先为了满足每个孩子至少有一个糖果，先将存储每个孩子糖果数的数组的元素都设为 $1$。
然后可以从 $1 \sim n$ 遍历孩子的评分，每次都去和他右边的孩子比较一下是否满足条件。这样**一轮**下来，就可以解决**一些**不满足要求的地方。不满足要求的情况有以下两种：
- 当前孩子比右边的评分高，但是糖果数却**小于等于**右边的孩子。
- 当前孩子比右边的评分低，但是糖果数却**大于等于**右边的孩子。
为了满足总和最小的情况，所以出现以上两种情况，就只需要在某个孩子的糖果数变成另一个孩子的糖果数加 $1$ 即可。
但是一轮下来，有可能在修改了某个孩子的糖果数后，由于每次只判断他的右边，可能左边的孩子又不满足要求了。要解决这种情况，只需要一直遍历直到所有孩子都满足要求即可。
容易证明，不会出现类似于[彭罗斯阶梯](https://baike.baidu.com/item/%E5%BD%AD%E7%BD%97%E6%96%AF%E9%98%B6%E6%A2%AF/10124603?fr=ge_ala)的情况，即无限循环。（彭罗斯阶梯可以这么理解：有 $n$ 层阶梯，高度为 $h_{1} \sim h_{n}$，然后出现了 $h_{1}<h_{2}$，$h_{2}<h_{3} \cdots$，最后 $h_{n}<h_{1}$ 的情况）。
最后，将所有孩子的糖果数加起来，就是本题的答案。
## AC Code
```cpp
#include<map>
#include<set>
#include<list>
#include<stack>
#include<queue>
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<unordered_set>
using namespace std;
#define endl '\n'
typedef long long ll;
const int N = 1e5 + 10;
typedef unsigned int ui;
typedef pair<int,int> pii;
typedef unsigned long long ull;
// ----------------------------
// ----------------------------
int candy[N];
int score[N];
// ----------------------------
int read() {
int f=1,sum=0;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){sum=(sum<<1)+(sum<<3)+(ch^48);ch=getchar();}
return sum * f;
}
void print(int x) {
if(x<0){putchar('-');x=-x;}
if(x>9)print(x/10);
putchar(char(x%10+'0'));
}
int main() {
int n = read();
for (int i=1;i<=n;i++) score[i] = read();
// ------------------------
for (int i=1;i<=n;i++) candy[i] = 1;
int cnt = 1; // 用于记录不满足要求的次数
while (cnt) {
cnt = 0;
for (int i=1;i<=n;i++) {
int r = i % n + 1;
// 发生不满足要求的两种情况
if (score[i]>score[r] && candy[i]<=candy[r]) {
candy[i] = candy[r] + 1;
cnt++;
}
else if (score[i]<score[r] && candy[i]>=candy[r]) {
candy[r] = candy[i] + 1;
cnt++;
}
}
}
int ans = 0;
for (int i=1;i<=n;i++) ans += candy[i];
// ------------------------
print(ans);
return 0;
}
```