C - Linear Approximation
題目大意:長度為n的序列,找任意一個整數(shù)b,使abs(a[i]-(i+b))的和最小卷要。
先將a[i]減去i,那么就是求a[i]-b的絕對值和最小.
轉換模型我們可以把a[i]看成數(shù)軸上的點,那么就是要求數(shù)軸上一個點到其他點的距離最小账月。
曾經(jīng)在藍書上看過這個結論,b這個點就是中位數(shù)方篮。
證明一波:
image.png
假設找的點是藍色點,向左移動d個單位,則左邊點到它的距離-d,右邊+d,那么-4d+2d=-2d減少了2d.
可見只要藍點左右兩邊點數(shù)不同就不是最優(yōu)解,那么使左右兩邊點數(shù)相同的就是這些點坐標的中位數(shù)了。
以上證明摘自藍書p6.
那么b為中位數(shù),我們就可以求出答案了。
#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;
}
