尝试写水题题解刷贡献分.jpg
根据小学生结论,一条数轴上离每个点距离和最小的那个点就是这些点最中间那个点。证明的话用微扰法就可以发现这是个下凸函数。
nmd,一开始记成了平均数WA了两次,实际上应该是中位数啦。
```cpp
int main(){
cin >> n ; int p ;
for (int i = 1 ; i <= n ; ++ i)
scanf("%d", &base[i]), k[i] = base[i] - i ;
sort(k + 1, k + n + 1) ;
if (n & 1) p = k[n / 2 + 1] ;
else p = (k[n / 2] + k[n / 2 + 1]) / 2 ;
for (int i = 1 ; i <= n ; ++ i)
ans += 1ll * abs(base[i] - p - i) ;
cout << ans << endl ; return 0 ;
}
```