csp信奥赛C++高频考点专项训练之贪心算法 --【线性扫描贪心】：均分纸牌

csp信奥赛C高频考点专项训练之贪心算法 --【线性扫描贪心】均分纸牌题目描述有N NN堆纸牌编号分别为1 , 2 , … , N 1,2,\ldots,N1,2,…,N。每堆上有若干张但纸牌总数必为N NN的倍数。可以在任一堆上取若干张纸牌然后移动。移牌规则为在编号为1 11堆上取的纸牌只能移到编号为2 22的堆上在编号为N NN的堆上取的纸牌只能移到编号为N − 1 N-1N−1的堆上其他堆上取的纸牌可以移到相邻左边或右边的堆上。现在要求找出一种移动方法用最少的移动次数使每堆上纸牌数都一样多。例如N 4 N4N4时4 44堆纸牌数分别为9 , 8 , 17 , 6 9,8,17,69,8,17,6。移动3 33次可达到目的从第三堆取4 44张牌放到第四堆此时每堆纸牌数分别为9 , 8 , 13 , 10 9,8,13,109,8,13,10。从第三堆取3 33张牌放到第二堆此时每堆纸牌数分别为9 , 11 , 10 , 10 9,11,10,109,11,10,10。从第二堆取1 11张牌放到第一堆此时每堆纸牌数分别为10 , 10 , 10 , 10 10,10,10,1010,10,10,10。输入格式第一行共一个整数N NN表示纸牌堆数。第二行共N NN个整数A 1 , A 2 , … , A N A_1,A_2,\ldots,A_NA1​,A2​,…,AN​表示每堆纸牌初始时的纸牌数。输出格式共一行即所有堆均达到相等时的最少移动次数。输入输出样例 1输入 14 9 8 17 6输出 13说明/提示对于100 % 100\%100%的数据1 ≤ N ≤ 100 1 \le N \le 1001≤N≤1001 ≤ A i ≤ 10000 1 \le A_i \le 100001≤Ai​≤10000。分析思路本题要求通过最少的相邻移动次数使所有堆的纸牌数相等。已知纸牌总数是堆数N的倍数因此平均值avg 总牌数 / N。贪心策略从左到右依次处理每一堆。若当前堆的纸牌数不等于avg则必须通过一次移动与右边相邻堆交换来调整。具体地计算当前堆与平均值的差值d a[i] - avg然后将这个差值移动到下一堆即a[i1] d同时移动次数加 1。这样处理后当前堆就变成了avg而差值的影响传递给了下一堆。继续处理下一堆直到最后一堆最后一堆必然已是avg无需再移动。正确性每次移动只涉及相邻两堆且保证已处理过的左边部分全部达到平均值不会因为后续调整而破坏。这种局部最优策略最终得到全局最优解移动次数即为需要调整的堆数即a[i] ! avg的堆数但不包括最后一堆。时间复杂度O(N)空间复杂度O(N)。代码实现#includebits/stdc.husingnamespacestd;intn;// 堆数inta[105];// 每堆纸牌数最大 N100开稍大一点ints,avg,ans;// s:总和, avg:平均值, ans:最少移动次数intmain(){cinn;for(inti1;in;i){cina[i];sa[i];// 累加总张数}avgs/n;// 计算平均值题目保证整除for(inti1;in;i){// 只处理到第 n-1 堆if(a[i]!avg){// 当前堆与平均值的差值移动到下一堆intda[i]-avg;a[i1]d;ans;// 发生一次移动}}coutansendl;return0;}功能分析输入第一行整数N1 ≤ N ≤ 100第二行N个整数表示每堆初始纸牌数1 ≤ Ai ≤ 10000处理计算总和s和平均值avg。从左到右扫描前N-1堆若当前堆不等于平均值则将其与平均值的差值可正可负加到下一堆并计数一次。输出计数结果。输出一个整数即最少移动次数。样例验证输入4 9 8 17 6总和 40avg 10i1: a[1]9 ≠10 → d-1 → a[2]8(-1)7, ans1i2: a[2]7 ≠10 → d-3 → a[3]17(-3)14, ans2i3: a[3]14 ≠10 → d4 → a[4]6410, ans3输出3与题目示例一致。各种学习资料助力大家一站式学习和提升#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信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新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;}