2020年CSP-X复赛真题及题解（T4：分糖果）-尧图网络科技

2020年CSP-X复赛真题及题解（T4：分糖果）

题目背景

老师组织一群孩子围成一个圈进行游戏，游戏结束后老师会根据每个孩子的表现进行评分并给予糖果奖励。

题目描述

每个孩子只能看见与自己相邻的2 22个孩子（左边的和右边的）的情况，只会关心相邻的且比自己评分低的同学的糖果数（如果相邻2 22个孩子的评分相等，则不关心）。为保证公平，相邻的孩子中，评分高的孩子必须获得更多的糖果(如果左右相邻2 22个孩子的评分相等，则不关心，即分最少的糖果1 11个）。同时，为鼓励孩子的积极性，每个孩子至少都能拿到1 11个糖果。现在需要你帮助老师来分发糖果，问怎么分配才能使要准备的糖果数最少？计算出需要的最少糖果数。

输入格式

输入有二行，第一行一个正整数n nn表示孩子的个数。

第二行n nn个非负整数，相邻的数用空格隔开，分别表示孩子的表现评分。

输出格式

一个整数，表示最少需要准备的糖果数。

输入输出样例 1

输入 1

3 1 2 0

输出 1

输入输出样例 2

输入 2

4 2 3 3 3

输出 2

说明/提示

【数据范围】

对于40 % 40\%40%的数据，1 ≤ n ≤ 100 1\leq n\leq 1001≤n≤100；

对于100 % 100\%100%的数据，1 ≤ n ≤ 10 5 1\leq n\leq 10^51≤n≤105;

所有评分都是0 00到100 100100之间的一个整数。

【样例解释】

样例一，分别分配2 , 3 , 1 2,3,12,3,1的糖果，所以最少需要6 66个糖果。

样例二，分别分配1 , 2 , 1 , 2 1,2,1,21,2,1,2的糖果，所以最少需要6 66个糖果。

思路分析

问题本质：环形相邻约束，评分高者糖果数必须严格大于评分低的邻居，评分相等无约束。目标是最小化总糖果数。
关键观察：
- 约束是有向的（低分 → 高分），且评分严格递增方向不可能形成环，因此可拓扑排序处理。
- 每个孩子的糖果数 =max(1, 所有低分邻居的糖果数 + 1)。
处理策略：
- 由于评分范围仅 0~100，按评分从小到大分组处理。
- 处理评分s的孩子时，所有评分< s的邻居已经计算完毕，可直接利用。
- 对每个孩子，检查左右邻居（环形取模），若邻居评分更低，则用其糖果数+1更新当前值，取最大值。
正确性：
- 每个孩子取的是满足所有低分邻居约束的最小值，因此全局总和最小。
- 评分相等互不影响，同一轮内不会互相依赖。
复杂度：O(n)，空间 O(n)，满足 n ≤ 1e5。

代码实现

#include<bits/stdc++.h>usingnamespacestd;intn,a[100005],c[100005];// a:评分, c:糖果数vector<int>v[105];// v[s]存储评分s的所有下标intmain(){cin>>n;for(inti=0;i<n;i++){cin>>a[i];v[a[i]].push_back(i);// 按评分分组}for(ints=0;s<=100;s++){// 评分从小到大for(inti:v[s]){intl=(i-1+n)%n,r=(i+1)%n;// 左右邻居下标（环形）c[i]=1;// 至少1个if(a[l]<a[i])c[i]=max(c[i],c[l]+1);// 左邻评分更低则必须比它多1if(a[r]<a[i])c[i]=max(c[i],c[r]+1);// 右邻评分更低则必须比它多1}}longlongans=0;for(inti=0;i<n;i++)ans+=c[i];cout<<ans;return0;}

功能分析

输入处理：读取孩子数n和评分数组，同时将每个下标按评分值存入vector，方便按评分升序处理。
核心计算：遍历评分0~100，对每个评分值下的所有孩子：
- 初始糖果为 1。
- 检查左右相邻的孩子（环形取模），若其评分更低，则当前孩子糖果数至少为低分邻居糖果数 + 1，取最大值。
- 由于评分升序处理，低分邻居的糖果值已经确定，保证依赖关系正确。
输出结果：累加所有糖果数并输出。
时间复杂度：O(n + 101)，空间 O(n)，满足n ≤ 1e5的要求。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整csp信奥赛C++学习资料）：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

https://edu.csdn.net/course/detail/41081 点击跳转

3、csp信奥赛高频考点知识详解及案例实践：

CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转

CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转

信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转

4、csp信奥赛冲刺一等奖有效刷题题解：

信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转

5、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

资讯详情