[??记录]ARC121D 1 or 2

**题意** ： 给定数组 $A_{1\sim n}$ ，你可以随意地把两个**未合并过**的数合并为一个数，合并后的数的值为这两个数的和。这里合并不要求相邻。 求合并后的新数组的极差的最小值。 $n\leq 5000$ ，时限$\texttt{2s}$。 ------------ 若某个数没有合并，可以看做与 $0$ 合并。于是枚举加入 $0$ 的个数，问题可转化为必须两两合并。 （通过转化为类似的形式，来统一题目的约束。这里把 1或2 利用 合并 统一为了 只有2） **结论** ：最优解一定是最大和最小匹配，次大和次小匹配，等等。 **证明** ：对于任意方案，若存在交错（而非包含）的匹配，则调整成包含的，极差不会增大。 具体地，对于 $a\leq b\leq c\leq d$ ，若 $(a,c),(b,d)$ 匹配，则调整为 $(a,d),(b,c)$ 匹配不劣，因为 $\min(a+c,b+d)=a+c\leq \min(a+d,c+b)$ ，$\max(a+c,b+d)=b+d\geq \max(a+d,c+b)$ 。 插入 $0$ 时还要维护顺序，用一点小伎俩，复杂度 $O(n^2)$ 。 ```cpp #include<algorithm> #include<cstdio> #define MaxN 5050 using namespace std; int n,a[MaxN]; int main() { scanf("%d",&n); for (int i=1;i<=n;i++)scanf("%d",&a[i]); sort(a+1,a+n+1); int p=0; while(a[p+1]<0&&p<n)p++; int ans=2000000000; for (int k=n&1;k<=n;k+=2){ int l=1000000000,r=-1000000000; #define get(x) ((x)<=p ? a[x] : (x)<=p+k ? 0 : a[(x)-k]) for (int i=1;i<=(n+k)/2;i++){ int now=get(i)+get(n+k-i+1); l=min(l,now);r=max(r,now); } ans=min(ans,r-l); }printf("%d",ans); return 0; } ```