2026年6月GESP真题及题解（C++五级）：排排坐

2026年6月GESP真题及题解C五级排排坐题目描述老师正在和小朋友们分糖果。小朋友们先在自己的手上写一个数字然后坐成一排。老师分发糖果的规则是每个小朋友获得自己以及左侧所有小朋友的手上数字之和个糖果。现在小朋友们都已经在自己手上写上了数字。请帮小朋友们安排合适的座位顺序使得小朋友们分到的糖果总量最大输出这个最大值。输入格式输入2 22行第一行为一个正整数n nn表示小朋友的个数第二行为n nn个正整数a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_na1​,a2​,⋯,an​表示小朋友们手上的数字整数之间以空格分隔。输出格式输出一个整数表示小朋友们可能分到的最大糖果总数量。输入输出样例 1输入 15 7 5 8 9 3输出 1111说明/提示样例解释小朋友安排座位后从左向右每人手上数字依次是9 , 8 , 7 , 5 , 3 9, 8, 7, 5, 39,8,7,5,3。这时可以得到最多的糖果( 9 ) ( 9 8 ) ( 9 8 7 ) ( 9 8 7 5 ) ( 9 8 7 5 3 ) 111 (9) (9 8) (9 8 7) (9 8 7 5) (9 8 7 5 3) 111(9)(98)(987)(9875)(98753)111。数据范围1 ≤ n ≤ 1000 1 \le n \le 10001≤n≤10001 ≤ a i ≤ 1000 1 \le a_i \le 10001≤ai​≤1000。思路分析问题转化设有排列p 1 , p 2 , … , p n p_1, p_2, \dots, p_np1​,p2​,…,pn​第 i 个小朋友得到的糖果数是前缀和S i ∑ j 1 i p j S_i \sum_{j1}^{i} p_jSi​∑j1i​pj​。总糖果数为∑ i 1 n S i ∑ i 1 n ( n − i 1 ) ⋅ p i \sum_{i1}^n S_i \sum_{i1}^n (n-i1) \cdot p_i∑i1n​Si​∑i1n​(n−i1)⋅pi​也就是说位置越靠左i 越小其数字被累加的次数越多权重越大。排序不等式为了最大化加权和应当将较大的数字放在权重较大的位置即按数字从大到小排列。因此只需将原数组降序排序然后计算∑ i 1 n ( n − i 1 ) ⋅ a i ′ \sum_{i1}^n (n-i1) \cdot a_i∑i1n​(n−i1)⋅ai′​其中a i ′ a_iai′​是降序排列后的数字。实现方式可以直接累加前缀和排序后从左到右维护当前前缀和pre每次将pre累加到答案ans中最终ans即为最大值。代码实现#includebits/stdc.husingnamespacestd;intn,a[1005];// n:人数, a:数字数组boolcmp(inta,intb){returnab;}intmain(){cinn;for(inti0;in;i)cina[i];sort(a,an,cmp);// 降序排序longlongans0,pre0;// ans:最终答案, pre:当前前缀和for(inti0;in;i){prea[i];// 更新前缀和anspre;// 将前缀和累加到答案中}coutans;// 输出最大总糖果数return0;}功能分析输入处理读取人数 n 和 n 个数字存入数组a。排序使用sort配合cmp函数将数组按从大到小排列保证最大的数字放在最左边权重最大。计算答案遍历排序后的数组维护pre当前位置及左侧所有数字之和每遍历一个位置就将pre累加到ans中。由于pre正好等于该位置小朋友获得的糖果数累加所有pre即得到总糖果数且因排序保证了最优。输出输出ans即为可能的最大值。各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整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;}