对于大小为1的集合，我们可以在其中加入0

因此，枚举0的个数，那么问题即可以看作要求每一个集合大小为2

（特别的，我们允许存在$\{0,0\}$，因为这样删除这两个0显然只会减小极差）

显然此时贪心将最小与最大、次小与次大……放入一个集合中即可

关于正确性，设最小值和最大值为$A,D$，若$\{A,D\}$则继续归纳即可，否则若$\{A,B\}$和$\{C,D\}$，那么有
$$
\begin{cases}\min(A+D,B+C)\ge \min(A+B,C+D)\\\max(A+D,B+C)\le \max(A+B,C+D)\end{cases}
$$
（关于这两个式子，左边的每一项都存在右边的一项小于等于或大于等于其）

因此不妨改为$\{A,D\}$和$\{B,C\}$，显然只会减小极差

具体实现可以先排序，再按照正负分开并加入0即可

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define N 5005
 4 vector<int>vn,vp;
 5 int n,mx,mn,ans,a[N];
 6 void add(int x){
 7     mx=max(mx,x);
 8     mn=min(mn,x);
 9 }
10 int main(){
11     scanf("%d",&n);
12     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
13     sort(a+1,a+n+1);
14     for(int i=1;i<=n;i++)
15         if (a[i]<=0)vn.push_back(a[i]);
16     for(int i=n;i;i--)
17         if (a[i]>0)vp.push_back(a[i]);
18     if (n&1)vn.push_back(0);
19     ans=2e9;
20     for(int i=(n&1);i<=n;i+=2,vn.push_back(0),vn.push_back(0)){
21         mx=-2e9,mn=2e9;
22         if (vn.size()<vp.size()){
23             for(int j=0;j<vn.size();j++)add(vn[j]+vp[j]);
24             for(int j=0;j<(vp.size()-vn.size())/2;j++)add(vp[vn.size()+j]+vp[vp.size()-j-1]);
25         }
26         else{
27             for(int j=0;j<vp.size();j++)add(vn[j]+vp[j]);
28             for(int j=0;j<(vn.size()-vp.size())/2;j++)add(vn[vp.size()+j]+vn[vn.size()-j-1]);
29         }
30         ans=min(ans,mx-mn);
31     }
32     printf("%d",ans);
33 }

View Code