Codeforces 394(#231 Div1) D. Physical Education and Buns

問題

n個の数が与えられる。自由に並べ替えてよい。
それぞれの数に対して何回でも+1または-1をすることができる。

1. 1, -1し終えたあとで、数が非減少な等差級数になっているようにしたい。

必要な+1, -1の回数の合計の最小値はいくつか。
およびその最小値を実現する等差級数の初項と公差を求めよ。

制約条件

n≦10^3
それぞれの数の絶対値≦10^4

方針

傾きが非負なので、まずは小さい順にソートしていい。
傾き（公差）dを固定する。
dを固定したら、そこから最大のずれ（直線とa[i]の差の絶対値）が最小になるような直線をa[i]の中に通したい。

この直線の切片の決め方はどうすればいいかというと、a[i] - d*iの最大と最小を見て、
(最大+最小)/2 + d*iをその直線にすればいい。

で、その直線がずれが最小の等差級数なので、全てのdの中で、
ずれの最大値 = （最大 - 最小 + 1) / 2が最小になるようなものを答えればいい。

ソースコード

int n, a[1000];

int main(){
	cin >> n;
	rep(i, n) cin >> a[i];
	sort(a, a + n);
	
	ll ans = inf, amx, amn, ad;
	
	for(int d = 0; d < 20010; d++){
		
		ll mn = inf, mx = -inf;
		rep(i, n){
			mn = min(mn, a[i] - (ll)d * i);
			mx = max(mx, a[i] - (ll)d * i);
		}
		if(ans > (mx - mn + 1) / 2){
			ans = (mx - mn + 1) / 2;
			amx = mx;
			amn = mn;
			ad = d;
		}
	}
	cout << ans << endl;
	cout << (amx + amn) / 2 << " " << ad << endl;
	
	return 0;
}