ARC121D 1 or 2

解题思路

首先考虑简化问题。

假设只能一次吃两个糖，那么显然可以贪心。

我们假设 \(n\) 是偶数，那么最优的就是排完序后首尾相加，依次向里靠拢。简单证明一下：

假设有 \(a<b<c<d\)，那么 \(\max(a+d,b+c)\leq\max(a+c,b+d)\)。\(\min\) 同理，所以我们的贪心是最优的。

我们再回来考虑原题。我们现在有可能只吃一个糖，如何转化为只能吃两颗糖呢？

其实很简单，只要不停加 \(0\) 就好了。注意可能有负数，因此要每次加完 \(0\) 在排个序。当序列长为偶数时计算即可。

时间复杂度 \(O(\frac{n^2 \log n}{2})\)。

代码

//Don't act like a loser.
//This code is written by huayucaiji
//You can only use the code for studying or finding mistakes
//Or,you'll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<'0'||ch>'9') {
		if(ch=='-')
			f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') {
		x=x*10+ch-'0';
		ch=getchar();
	}
	return f*x;
}

const int MAXN=10000+10;

int n,m,ans=1e18;
int a[MAXN];

int check(int n) {
	int maxx=-1e18,minn=1e18;
	for(int i=n,j=1;i>j;i--,j++) {
		maxx=max(maxx,a[i]+a[j]);
		minn=min(minn,a[i]+a[j]);
	}
	return maxx-minn;
}

bool cmp(int x,int y) {
	return x>y;
}

signed main() {
	cin>>n;
	for(int i=1;i<=n;i++) {
		a[i]=read();
	}
	
	m=n;
	
	for(int i=0;i<=n;i++) {
		if(m%2==0) {
			sort(a+1,a+m+1,cmp);
			ans=min(ans,check(m));
		}
		a[++m]=0;
	}
	
	cout<<ans<<endl;
	return 0;
}