2025年【江苏“信息与未来”编程思维】真题及题解（T3：美味水果）

2025年【江苏“信息与未来”编程思维】真题及题解T3美味水果题目描述Dr. X 收到了一份礼物n nn个水果其中第i ii个水果的好吃程度为x i x_ixi​。新鲜的水果会随时间变得不如最初好吃每天Dr. X 可以选择吃掉一个水果并记录下该天吃掉的水果的好吃程度。没有被吃掉的每个水果好吃程度将在第二天变为y ⌊ x ⌋ y \lfloor\sqrt x\rfloory⌊x​⌋即 “开根号取整”y yy是满足y 2 ≤ x y^2 ≤ xy2≤x的最大整数。请计算在所有可能的吃水果顺序中Dr. X 最多能获得多少好吃程度的总和。输入格式输入包含两行第一行一个整数n nn表示水果数量第二行n nn个用空格分隔的整数x 1 , x 2 , ⋯ , x n x_1 , x_2 , \cdots, x_nx1​,x2​,⋯,xn​表示每个水果的初始好吃程度。输出格式输出一个整数表示能够获得的好吃程度总和的最大值。输入输出样例 1输入 12 100 10输出 1103输入输出样例 2输入 26 1 3 7 10 15 21输出 228说明/提示样例 1 解释在第一天Dr.X 吃掉第一个水果好吃程度为100 100100另一个水果在第二天吃好吃程度为⌊ 10 ⌋ 3 \lfloor\sqrt{10}\rfloor 3⌊10​⌋3吃完所有水果好吃程度的总和为103 103103。数据范围对于40 % 40\%40%的数据1 ≤ n ≤ 100 1 ≤ n ≤ 1001≤n≤100。对于100 % 100\%100%的数据1 ≤ n ≤ 10 5 1 ≤ n ≤ 10^51≤n≤105水果的好吃程度1 ≤ x i ≤ 10 9 1 ≤ x_i ≤ 10^91≤xi​≤109。思路分析1. 问题本质共有 n 个水果第 i 个初始好吃度为x i x_ixi​。每天必须吃掉一个其余所有水果的好吃度都会变为⌊ x ⌋ \lfloor\sqrt{x}\rfloor⌊x​⌋。我们要决定每天吃哪个使得所有被吃掉时的好吃度之和最大。2. 贪心策略的推导假设在某一天有两个水果 A 和 B且当前值分别为a ≥ b a \ge ba≥b。若我们先吃 A则第二天 B 的值变为f ( b ) ⌊ b ⌋ f(b)\lfloor\sqrt{b}\rfloorf(b)⌊b​⌋两天总贡献为 a f(b)。若先吃 B则第二天 A 的值变为 f(a)总贡献为 b f(a)。比较两者( a f ( b ) ) − ( b f ( a ) ) ( a − b ) − ( f ( a ) − f ( b ) ) (a f(b)) - (b f(a)) (a - b) - (f(a) - f(b))(af(b))−(bf(a))(a−b)−(f(a)−f(b))因为f ( x ) ⌊ x ⌋ f(x)\lfloor\sqrt{x}\rfloorf(x)⌊x​⌋是单调递增且满足x − f ( x ) x - f(x)x−f(x)非递减可验证所以当a ≥ b a \ge ba≥b时a − f ( a ) ≥ b − f ( b ) a - f(a) \ge b - f(b)a−f(a)≥b−f(b)即a − b ≥ f ( a ) − f ( b ) a - b \ge f(a) - f(b)a−b≥f(a)−f(b)。因此上式≥ 0 \ge 0≥0即先吃大的不会比先吃小的差。由归纳可知每天选择当前值最大的水果吃掉是最优策略。3. 退化过程的单调性若初始值x ≥ y x \ge yx≥y则经过相同次数的开根号取整后仍有f k ( x ) ≥ f k ( y ) f^k(x) \ge f^k(y)fk(x)≥fk(y)因为 f 单调。因此初始值较大的水果在任何时刻都不会比初始值较小的水果变得“更小”。所以我们只需将初始好吃度从大到小排序然后第 i 个从0开始水果在第 i1 天被吃掉它经历的退化次数正好为 i即开根号 i 次。4. 退化次数与计算量对于x ≤ 10 9 x \le 10^9x≤109开根号取整后数值急剧下降10 9 → 31622 → 177 → 13 → 3 → 1 10^9 \to 31622 \to 177 \to 13 \to 3 \to 1109→31622→177→13→3→1最多只需 5 次就变成 1之后不再变化。因此对于每个水果我们只需模拟至多 i 次开根号但 i 最大可达10 5 10^5105若每个都模拟 i 次会超时。优化由于当值变为 1 后继续开根号仍是 1所以我们可在模拟中一旦 (v1) 就停止剩余退化次数不影响结果。这样每个水果实际循环次数不超过 5 次总计算量O ( n ⋅ 5 ) O(n \cdot 5)O(n⋅5)。5. 最终算法步骤读入 n 和数组 a。将数组降序排序。初始化答案 (ans0)。遍历排序后的数组对第 (i) 个元素令 v a[i](t i)需要开根号的次数。当 t 0 且 v 1 时执行v ⌊ v ⌋ v \lfloor\sqrt{v}\rfloorv⌊v​⌋t 减 1。将最终 v 累加到答案。输出 ans。代码实现#includebits/stdc.husingnamespacestd;// 自定义比较函数降序排列boolcmp(inta,intb){returnab;}intmain(){ios::sync_with_stdio(false);cin.tie(0);intn;cinn;vectorinta(n);for(inti0;in;i)cina[i];sort(a.begin(),a.end(),cmp);// 降序排序longlongans0;// 总好吃度用 long long 防溢出for(inti0;in;i){intva[i];// 当前水果的初始值intti;// 需要退化的天数开根号次数while(t0v1){// 一旦 v 变为 1 就不再变化v(int)sqrt(v);// 开根号取整--t;}ansv;// 累加贡献}coutans;return0;}功能分析正确性基于贪心证明每天选择当前最大值是最优的利用单调性排序后按顺序吃即可等价模拟。每个水果的退化模拟精确计算了其被吃时的实际值累加即得最优总和。时间复杂度排序O ( n log ⁡ n ) O(n\log n)O(nlogn)退化模拟每个水果最多循环 5 次因为 v 很快降到 1故总时间O ( n log ⁡ n ) O(n\log n)O(nlogn)。【秘籍汇总】完整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;}