command_block 的博客

command_block 的博客

[??记录]ARC121D 1 or 2

posted on 2021-10-28 21:47:43 | under 记录 |

题意 : 给定数组 $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)$ 。

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