题目大意:这次比赛所有的题目都描述的很简单,我这种英语不好的也能一看就懂。给你N个数存为Ai,请你给出一个b,使abs(A1−(b+1))+abs(A2−(b+2))+…+abs(AN−(b+N))最小,输出这个最小值。
思路:一看到绝对值,就应该想到数轴上点之间的距离,这道题虽然给b加上了i,但只要把式子拆开,一开始就把每个Ai减去i就行了。然后可以证明(或者学过)一个点到其他点距离和最短应该是这些点坐标集合的中位数,然后直接写就行了。(一定要记得用long long!)
AC程序
//库省略const int maxn=200005;ll n,d,k;ll a[maxn];int main(){ cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; a[i]-=i; } sort(a+1,a+n+1); ll b=0; if(n%2==0) b=(a[n/2]+a[n/2+1])/2; else b=a[n/2+1]; ll ans=0; for(int i=1;i<=n;i++) { ans=ans+abs(b-a[i]); } cout<<