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

2020年CSP-X复赛真题及题解T4分糖果题目背景老师组织一群孩子围成一个圈进行游戏游戏结束后老师会根据每个孩子的表现进行评分并给予糖果奖励。题目描述每个孩子只能看见与自己相邻的2 22个孩子左边的和右边的的情况只会关心相邻的且比自己评分低的同学的糖果数如果相邻2 22个孩子的评分相等则不关心。为保证公平相邻的孩子中评分高的孩子必须获得更多的糖果(如果左右相邻2 22个孩子的评分相等则不关心即分最少的糖果1 11个。同时为鼓励孩子的积极性每个孩子至少都能拿到1 11个糖果。现在需要你帮助老师来分发糖果问怎么分配才能使要准备的糖果数最少计算出需要的最少糖果数。输入格式输入有二行第一行一个正整数n nn表示孩子的个数。第二行n nn个非负整数相邻的数用空格隔开分别表示孩子的表现评分。输出格式一个整数表示最少需要准备的糖果数。输入输出样例 1输入 13 1 2 0输出 16输入输出样例 2输入 24 2 3 3 3输出 26说明/提示【数据范围】对于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。代码实现#includebits/stdc.husingnamespacestd;intn,a[100005],c[100005];// a:评分, c:糖果数vectorintv[105];// v[s]存储评分s的所有下标intmain(){cinn;for(inti0;in;i){cina[i];v[a[i]].push_back(i);// 按评分分组}for(ints0;s100;s){// 评分从小到大for(inti:v[s]){intl(i-1n)%n,r(i1)%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}}longlongans0;for(inti0;in;i)ansc[i];coutans;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}