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

题意概述给定一个长度为n nn的数列{ a i } \{a_i\}{ai​}将a i a_iai​改为b bb所需的代价是( a i − b ) 2 (a_i-b)^2(ai​−b)2。求使得max ⁡ { a i } − min ⁡ { a i } ≤ 17 \max\{a_i\}-\min\{a_i\}\le17max{ai​}−min{ai​}≤17所需的最小代价。解题思路考虑三分法。如果不会三分法右转 OI Wiki 学一学。设要将数列的所有元素修改到[ x , x 17 ] [x,x17][x,x17]区间内则代价即为关于x xx的函数f ( x ) f(x)f(x)。问题转化求f ( x ) f(x)f(x)在[ min ⁡ { a i } , max ⁡ { a i } − 17 ] [\min\{a_i\},\max\{a_i\}-17][min{ai​},max{ai​}−17]区间上的最小值。显然若[ x , x 17 ] [x,x17][x,x17]的范围超出了数列的取值范围则一定不会更优。由题意得f ( x ) ∑ i 1 n c o s t i ( x ) f(x)\sum_{i 1}^{n}cost_i(x)f(x)i1∑n​costi​(x)其中c o s t i ( x ) cost_i(x)costi​(x)为元素a i a_iai​产生的代价是关于x xx的函数为c o s t i ( x ) { ( a i − x ) 2 ( a i x ) , 0 ( x ≤ a i ≤ x 17 ) , ( a i − x − 17 ) 2 ( a i x 17 ) . cost_i(x) \begin{cases} (a_i - x)^2(a_ix),\\ 0(x\leq a_i\leq x 17),\\ (a_i - x - 17)^2(a_ix 17). \end{cases}costi​(x)⎩⎨⎧​(ai​−x)20(ai​−x−17)2​(ai​x),(x≤ai​≤x17),(ai​x17).​c o s t i ( x ) cost_i(x)costi​(x)的图像如下图所示很显然这是一个单谷函数。因为单谷函数的和还是单谷函数所以f ( x ) f(x)f(x)也是单谷函数。于是可以直接使用三分法求解最小值。时间复杂度O ( n log ⁡ n ) O(n\log n)O(nlogn)。Code#includeiostreamusingnamespacestd;constintN1000;constintINF0x3f3f3f3f;inta[N],n;intf(intx){ints0;for(inti0;in;i){if(a[i]x)s(x-a[i])*(x-a[i]);elseif(a[i]x17)s(a[i]-x-17)*(a[i]-x-17);}returns;}intmain(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);intlINF,r-INF,m1,m2;cinn;for(inti0;in;i){cina[i];lmin(l,a[i]);rmax(r,a[i]);}r-17;while(lr){m1(lr1),m2m11;if(f(m1)f(m2))rm2-1;elselm11;}coutf(l);return0;}Update 2025.2.11笔误单峰函数→ \to→单谷函数。Update 2025.6.15更换图片更改图片与文字间距。Update 2025.6.16修改部分公式格式。Update 2025.12.6微调格式优化语言表达。