题解：洛谷 P3650 [USACO1.3] 滑雪课程设计Ski Course Design

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P3650 [USACO1.3] 滑雪课程设计Ski Course Design - 洛谷【题目描述】农民约翰的农场里有n座山峰每座山都有一个在 0 到 100 之间的整数的海拔高度。在冬天因为山上有丰富的积雪约翰经常开办滑雪训练营。不幸的是约翰刚刚得知税法在滑雪训练营方面有新变化明年开始实施。在仔细阅读法律后他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于 17 就要收税。因此如果他改变山峰的高度使最高与最低的山峰海拔高度差不超过 17 约翰可以避免支付税收。如果改变一座山x单位的高度成本是x^2 单位约翰最少需要付多少钱才能使海拔最高的山峰与海拔最低的山峰的高度只差不超过 17 约翰只愿意改变整数单位的高度。【输入】输入的第一行是一个整数代表山峰的数量n。第 2 行到n1行每行一个整数。第i行的整数ai代表第i座山的海拔高度。【输出】输出一行一个整数代表约翰需要支付修改山海拔高度的总金额。【输入样例】5 20 4 1 24 21【输出样例】18【核心思想】问题分析给定n nn座山峰的海拔高度a i ∈ [ 0 , 100 ] a_i \in [0, 100]ai​∈[0,100]要求将所有山峰高度调整到某个区间[ L , L 17 ] [L, L17][L,L17]内L LL为整数使得调整总成本∑ x i 2 \sum x_i^2∑xi2​最小其中x i x_ixi​为每座山调整的高度。这是一个枚举 贪心问题关键在于确定最优区间下界L LL。算法选择排序预处理将山峰高度从小到大排序便于按区间处理枚举区间下界由于原始高度范围[ 0 , 100 ] [0, 100][0,100]最优区间[ L , L 17 ] [L, L17][L,L17]的L LL只需枚举[ 0 , 83 ] [0, 83][0,83]因L 17 ≤ 100 L17 \leq 100L17≤100贪心调整对每个L LL低于L LL的山峰提升到L LL高于L 17 L17L17的山峰降低到L 17 L17L17区间内的山峰不动关键步骤读入数据n nn和数组a [ 1.. n ] a[1..n]a[1..n]排序将a aa按升序排列枚举下界L LLL LL从0 00到83 8383初始化sum 0遍历每座山a j a_jaj​若a j L a_j Laj​Lsum (L - a_j)^2提升到L LL若a j L 17 a_j L 17aj​L17sum (a_j - L - 17)^2$降低到L 17 L17L17若在[ L , L 17 ] [L, L17][L,L17]内不调整成本为 0更新答案minn min(minn, sum)输出结果最小总成本m i n n minnminn时间/空间复杂度时间复杂度O ( 84 ⋅ n ) O ( n ) O(84 \cdot n) O(n)O(84⋅n)O(n)枚举 84 个下界每个遍历n nn座山空间复杂度O ( n ) O(n)O(n)存储山峰高度数组枚举区间的核心思想区间长度固定题目要求极差≤ 17 \leq 17≤17即区间长度固定为 17只需确定下界L LL最优调整策略对于固定区间[ L , L 17 ] [L, L17][L,L17]每座山独立决策——低于下限就提到下限高于上限就降到上限区间内不动。这是因为在区间约束下每座山的最优调整就是投影到区间最近端点枚举范围压缩原始高度∈ [ 0 , 100 ] \in [0, 100]∈[0,100]L LL的有效范围仅为[ 0 , 83 ] [0, 83][0,83]枚举量极小凸成本特性成本函数x 2 x^2x2是凸函数投影到区间的策略在独立约束下是最优的适用于带区间约束的最小化调整、固定窗口滑动、离散枚举优化等问题【解题思路】【算法标签】#普及- #贪心【代码详解】#includebits/stdc.husingnamespacestd;intn,a[1005],minn1e9;intmain(){cinn;// 输入nfor(inti1;in;i){// 输入所有山峰高度cina[i];}sort(a1,an1);// 按照从大到小排序for(inti0;i83;i){// 遍历山峰的最小高度最高高度就是i17intsum0;// 定义每轮总金额初始为0for(intj1;jn;j){// 遍历所有山峰if(a[j]i){// 小于最小高度就增加两者之差需要的成本sum(i-a[j])*(i-a[j]);}elseif(a[j]i17){// 高于最大高度也增加两者之差需要的成本sum(a[j]-i-17)*(a[j]-i-17);}}minnmin(minn,sum);// 每轮统计后计算最小值}coutminnendl;// 输出最小值return0;}【运行结果】5 20 4 1 24 21 18