题解 [ARC121D] 1 or 2

诈骗题，竟然评到了 \(2784\) 的惊人高分（快到红了），来补个题解。

题意：有两个可重集 \(A,B\)，\(B\) 初始为 \(\varnothing\)。每次从 \(A\) 中删除一个或两个数，并将它们的和加入 \(B\) 中，重复操作直到 \(A=\varnothing\)。最小化 \(B\) 的极差。

\(1\le |A|\le 5\times 10^3\)。

如果每次必须删除两个数，显然最小与最大、次小与次大配对是最优的，可以用交换法证明。观察到删除一个数的操作等价于删除 \(0\) 和那个数。因此枚举有多少次删除一个数的操作，补充那么多个 \(0\) 之后跑刚刚的贪心即可。

容易做到 \(\Theta(n^2)\)，但我懒得做到，所以写了一个 \(\Theta(n^2\log n)\)。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(ll x=(y);x<=(z);x++)
#define per(x,y,z) for(ll x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;
const ll N = 1e4+5, inf = 0x3f3f3f3f3f3f3f3fll;

ll n, a[N], b[N], ans = inf;
template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

int main() {
	scanf("%lld", &n);
	rep(i, 1, n) scanf("%lld", &a[i]);
	rep(i, 0, n) {
		ll L = 1, R = n + i;
		if((R - L + 1) & 1) continue;
		rep(j, 1, n) b[j] = a[j];
		rep(j, n+1, n+i) b[j] = 0;
		sort(b+1, b+1+n+i);
		ll mn = inf, mx = -inf;
		while(L < R) {
			chkmin(mn, b[L] + b[R]);
			chkmax(mx, b[L] + b[R]);
			++L; --R;
		}
		chkmin(ans, mx - mn);
	}
	printf("%lld\n", ans);
	return 0;
}