尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
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;}
RELATED

相关推荐

Qwen2.5-VL行业微调:物理归一化与跨模态对齐器重训实战

Qwen2.5-VL行业微调:物理归一化与跨模态对齐器重训实战

1. 项目概述:为什么在特殊行业数据上微调Qwen2.5-VL不是“跑通就行”的事 Qwen2.5-VL是通义千问系列中首个真正意义上支持 端到端多模态理解与生成 的开源大模型,它不像早期VLM那样把图像特征硬塞进纯文本LLM的输入层,而是通过一个可学习的…

📅 2026/11/15 5:16:34
简悦4.0.2:面向深度阅读者的认知增强系统

简悦4.0.2:面向深度阅读者的认知增强系统

1. 项目概述:这不是一个“AI阅读插件”,而是一套面向深度阅读者的认知增强系统“简悦插件 阅读助手 4.0.2 版 - 已全面接入GPT 4.1最新模型”——这个标题里藏着三个被多数人忽略的关键信号:“简悦”不是通用浏览器插件,而是专注学…

📅 2026/11/16 8:35:33
国产大模型编程实战:上下文保真度与框架锚定能力评测

国产大模型编程实战:上下文保真度与框架锚定能力评测

1. 这不是选模型,是选“编程搭档”:国产大模型在真实编码场景中的生存实录最近两周,我连续帮三个创业团队重构了他们的内部AI编程协作流程。不是写个demo,而是把AI真正嵌进需求评审、PR Review、单元测试生成、遗留系统文档补全这…

📅 2026/11/15 10:33:21
MORE NEWS

更多资讯

📰

天猫上电工证过期了在哪考?复审延期全攻略

天猫上电工证过期了在哪考?复审延期全攻略 证书过期了不知道怎么复审延期?这事儿真的让不少人头疼。你手上那本【天猫上电工证】要是没按时复审,不仅影响工作,还可能被单位或项目清退。别慌,下面一步步教你搞清楚怎么操作,同时还能帮你选对【在哪考】的…

📰

济阳电工证复审保姆级教程:电工证复审全攻略来了

济阳电工证复审保姆级教程:电工证复审全攻略来了 你是不是也遇到了这样的情况?手头的电工证快到期了,却不知道怎么复审,生怕耽误了找工作,甚至被单位开除?别急,今天就给你讲讲【济阳电工证复审】的保姆级教程,让你轻松应对复审流程,顺利拿到新证,继…

📰

你知道考电工证现场操作什么吗?内部消息告诉你怎么避坑

你知道考电工证现场操作什么吗?内部消息告诉你怎么避坑 怕考不过白交培训费?别急,这波内部消息我来告诉你,考电工证现场到底操作什么,还有哪些避坑点,别再被培训机构忽悠了。…

📰

电工证社会化定级实操考试考什么 官方报名入口你知道吗

电工证社会化定级实操考试考什么 官方报名入口你知道吗 怕考不过白交培训费,我来帮你搞清楚电工证社会化定级到底考啥,别再被培训机构忽悠了。现在全国多地都在推进电工证社会化定级改革,尤其是郑州、洛阳等地,已经逐步落实。如果你是洛阳涧西区的应届工…

📰

电工证证属于国家级吗最新政策解读

电工证属于国家级吗?考前押题帮你搞定跨省转证难题 之前考的证在外省能不能转过来?这是很多电工从业者最头疼的问题之一,尤其是在河南信阳浉河区从事公路工程的电工来说,跨省转证、考试、继续教育、甚至薪资待遇都成了绕不开的话题。这篇文章我们就从【电…

📰

电工证考好了几天拿证怎么报名才不踩坑

电工证考好了几天拿证怎么报名才不踩坑 证书过期了不知道怎么复审延期,这事儿别急,我给你整明白了。很多电工朋友都遇到过这种情况,尤其是河南的建筑工人,手里拿着电工证,干着活,结果证到期了没人提醒,一查才发现已经不能用了。这不,今天我就以一个河…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬