csp信奥赛C++高频考点专项训练之贪心算法 --【跳跃与过河问题】：跳跳！

csp信奥赛C高频考点专项训练之贪心算法 --【跳跃与过河问题】跳跳题目描述你是一只小跳蛙你特别擅长在各种地方跳来跳去。这一天你和朋友小 F 一起出去玩耍的时候遇到了一堆高矮不同的石头其中第i ii块的石头高度为h i h_ihi​地面的高度是h 0 0 h_0 0h0​0。你估计着从第i ii块石头跳到第j jj块石头上耗费的体力值为( h i − h j ) 2 (h_i - h_j) ^ 2(hi​−hj​)2从地面跳到第i ii块石头耗费的体力值是( h i ) 2 (h_i) ^ 2(hi​)2。为了给小 F 展现你超级跳的本领你决定跳到每个石头上各一次并最终停在任意一块石头上并且小跳蛙想耗费尽可能多的体力值。当然你只是一只小跳蛙你只会跳不知道怎么跳才能让本领更充分地展现。不过你有救啦小 F 给你递来了一个写着 AK 的电脑你可以使用计算机程序帮你解决这个问题万能的计算机会告诉你怎么跳。那就请你——会写代码的小跳蛙——写下这个程序为你 NOIp AK 踏出坚实的一步吧输入格式输入一行一个正整数n nn表示石头个数。输入第二行n nn个正整数表示第i ii块石头的高度h i h_ihi​。输出格式输出一行一个正整数表示你可以耗费的体力值的最大值。输入输出样例 1输入 12 2 1输出 15输入输出样例 2输入 23 6 3 5输出 249说明/提示样例解释两个样例按照输入给定的顺序依次跳上去就可以得到最优方案之一。数据范围对于1 ≤ i ≤ n 1 \leq i \leq n1≤i≤n有0 h i ≤ 10 4 0 h_i \leq 10 ^ 40hi​≤104且保证h i h_ihi​互不相同。对于10 % 10\%10%的数据n ≤ 3 n \leq 3n≤3对于20 % 20\%20%的数据n ≤ 10 n \leq 10n≤10对于50 % 50\%50%的数据n ≤ 20 n \leq 20n≤20对于80 % 80\%80%的数据n ≤ 50 n \leq 50n≤50对于100 % 100\%100%的数据n ≤ 300 n \leq 300n≤300。思路分析这是一道贪心 排序的题目。为了消耗最多的体力值每次跳跃都应选择与当前石头高度差最大的未访问石头。由于体力值与高度差的平方成正比平方函数是凸函数因此极端值最高、最低之间的差会产生最大的平方值。贪心策略将所有石头按高度升序排序。从地面出发先跳到最高的石头因为地面高度为0跳最高得到最大平方。然后跳到当前最低的石头再跳到当前最高的石头依此类推形成“之”字形路径。使用两个指针l和r分别指向未访问的最低和最高石头交替访问直到所有石头都被跳过。这样每一步都保证了当前石头与上一次石头的差值尽可能大从而总体力值最大。代码实现#includebits/stdc.husingnamespacestd;longlongn,a[310];intmain(){cinn;for(inti1;in;i)cina[i];sort(a1,an1);//升序排序范围[1, n]longlongans0;//体力值可能很大用long longintl1,rn;//左右指针指向未跳的石头intcur0;//当前所在高度初始为地面0boolflagtrue;//true表示下次取最大false表示取最小while(lr){if(flag){//取当前最大高度的石头ans(a[r]-cur)*(a[r]-cur);cura[r];r--;}else{//取当前最小高度的石头ans(a[l]-cur)*(a[l]-cur);cura[l];l;}flag!flag;//交替方向}coutansendl;return0;}功能分析输入第一行整数 n石头个数n ≤ 300第二行 n 个互不相同的正整数高度 ≤ 10000。处理将石头高度存入数组 a[1…n] 并升序排序。初始化当前高度 cur 0地面左右指针 l1最小rn最大。交替选择当前最大和最小石头跳跃从当前高度跳到最大石头若 flagtrue从当前高度跳到最小石头若 flagfalse每次跳跃后更新 cur 为落脚点高度并移动对应指针。循环直到所有石头都被跳过l r。输出最大可能消耗的体力值整数。正确性贪心策略保证每次跳跃选择极端高度差平方函数凸性使得总和最大。复杂度O(n log n) 时间O(1) 额外空间不计输入数组。各种学习资料助力大家一站式学习和提升#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;}