Codeforces 238B Boring Partition

問題

n個の数列a[i]を互いに素な二つのグループにわける。片方が空であってもよい。
f(i, j)を、i, jが違うグループのときa[i] + a[j] + h,
同じグループのときa[i] + a[j]とする。

max{f(i, j) | 1≦i＜j≦n} - min{f(i, j) | 1≦i＜j≦n}が最小となるようなわけ方をどれか一つ出力せよ。

制約条件

n≦10^5
h≦10^8

方針

要素は小さい順にソートされてるとして考える。
全部がAであるとき、min = a[0] + a[1], maxf = a[n-1] + a[n-2]
ここからmax-minを減らしたい。
a[n-2]をBに移してしまうとmaxfがhだけ増えるので移さないほうがいい。

なので最小値のほうだけ移して最小値を上げるようになる。
nがある程度大きい場合、a[0]とa[1]を同時に移すと最小値は変わらないので、
a[0]とa[1]を同時には移さないような場合だけ全部考えればいい。

以下では、小さいほうから6つの要素の選び方を全通り試している。

ソースコード

int n, h, a[100000], res[100000];

int main(){
	cin >> n >> h;
	rep(i, n) cin >> a[i];
	
	int ans = inf, ansi = 0;
	vector<pi> v;
	rep(i, n) v.pb(mp(a[i], i));
	sort(all(v), greater<pi>());
	
	rep(i, 1 << 6){
		int mx = 0, mn = inf;
		vi l, r;
		rep(j, min(n, 6)){
			if(i & 1 << j) l.pb(v[n - 1 - j].first);
			else r.pb(v[n - 1 - j].first);
		}
		if(n > 6) l.pb(v[0].first);
		if(n > 7) l.pb(v[1].first);
		
		sort(all(l));
		sort(all(r));
		//cerr<<l.size()<<" "<<r.size()<<" "<<i<<" "<<n<<endl;
		rep(j, l.size()) rep(k, r.size()){
			mx = max(mx, l[j] + r[k] + h);
			mn = min(mn, l[j] + r[k] + h);
		}
		rep(j, l.size()) rep(k, j){
			mx = max(mx, l[j] + l[k]);
			mn = min(mn, l[j] + l[k]);
		}
		rep(j, r.size()) rep(k, j){
			mx = max(mx, r[j] + r[k]);
			mn = min(mn, r[j] + r[k]);
		}
		if(ans > mx - mn){
			ans = mx - mn;
			ansi = i;
		}
	}
	rep(i, min(n, 6)) res[v[n - 1 - i].second] = ansi & 1 << i ? 1 : 2;
	for(int i = 6; i < n; i++) res[v[n - 1 - i].second] = 1;
	cout << ans << endl;
	rep(i, n) cout << res[i] << " ";
	cout << endl;
	
	return 0;
}