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; }