题意概述

给定一个长度为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,x+17][x,x+17]区间内，则代价即为关于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,x+17][x,x+17]的范围超出了数列的取值范围，则一定不会更优。

由题意得：
f ( x ) = ∑ i = 1 n c o s t i ( x ) f(x)=\sum_{i = 1}^{n}cost_i(x)f(x)=i=1∑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_i<x),\\ 0&(x\leq a_i\leq x + 17),\\ (a_i - x - 17)^2&(a_i>x + 17). \end{cases}costi​(x)=⎩⎨⎧​(ai​−x)20(ai​−x−17)2​(ai​<x),(x≤ai​≤x+17),(ai​>x+17).​
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

#include<iostream>usingnamespacestd;constintN=1000;constintINF=0x3f3f3f3f;inta[N],n;intf(intx){ints=0;for(inti=0;i<n;++i){if(a[i]<x)s+=(x-a[i])*(x-a[i]);elseif(a[i]>x+17)s+=(a[i]-x-17)*(a[i]-x-17);}returns;}intmain(){ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);intl=INF,r=-INF,m1,m2;cin>>n;for(inti=0;i<n;++i){cin>>a[i];l=min(l,a[i]);r=max(r,a[i]);}r-=17;while(l<r){m1=(l+r>>1),m2=m1+1;if(f(m1)<f(m2))r=m2-1;elsel=m1+1;}cout<<f(l);return0;}

Update 2025.2.11：笔误，单峰函数→ \to→单谷函数。
Update 2025.6.15：更换图片，更改图片与文字间距。
Update 2025.6.16：修改部分公式格式。
Update 2025.12.6：微调格式，优化语言表达。