C - Linear Approximation
题目大意:长度为n的序列,找任意一个整数b,使abs(a[i]-(i+b))的和最小。
先将a[i]减去i,那么就是求a[i]-b的绝对值和最小.
转换模型我们可以把a[i]看成数轴上的点,那么就是要求数轴上一个点到其他点的距离最小。
曾经在蓝书上看过这个结论,b这个点就是中位数。
证明一波:
image.png
假设找的点是蓝色点,向左移动d个单位,则左边点到它的距离-d,右边+d,那么-4d+2d=-2d减少了2d.
可见只要蓝点左右两边点数不同就不是最优解,那么使左右两边点数相同的就是这些点坐标的中位数了。
以上证明摘自蓝书p6.
那么b为中位数,我们就可以求出答案了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#define ll long long
#define out(a) printf("%lld ",a)
using namespace std;
int n;
int num;
ll ans;
int a[200050];
int read()
{
int s=0,t=1; char c;
while (c<'0'||c>'9'){if (c=='-') t=-1; c=getchar();}
while (c>='0'&&c<='9'){s=s*10+c-'0'; c=getchar();}
return s*t;
}
int main()
{
n=read();
for (int i=1;i<=n;i++)
a[i]=read(),a[i]-=i;
sort(a+1,a+n+1);
if (n&1) num=a[n/2+1];
else num=a[n/2];
for (int i=1;i<=n;i++)
ans+=abs(a[i]-num);
out(ans);
return 0;
}
