ARC121D 1 or 2
诈骗题。
思路
吃一个糖的操作可以看做是和一个 \(a_i\) 为 0 的糖一起吃。
可以枚举有多少个糖单独吃来确定要增加多少个 0。
问题变为每次吃两颗糖。
根据人类直觉，有一个贪心，最小的糖和最大的糖一起吃最优，次小的糖和次大的糖一起吃最优，依次类推。
怎么证明这个性质呢？
有 2 个理解方法：
感性理解：
使最大值最小，那么最大的数肯定加上最小的数最优；最小值最大，那么最小的数加上最大的数最优；应该可以理解以上结论。
理性理解：
有 \(A<B<C<D\)。
可以选 \(A+D,B+C\)，同时也可以选 \(A+C,B+D\)。（\(A+B,C+D\) 肯定不优，故不考虑）
有 \(|(A+D)-(B+C)|\) 和 \(|(A+C)-(B+D)|\)。
\[|(A+D)-(B+C)|=|A-B+D-C|
\]
\[|(A+C)-(B+D)|=|A-B+C-D|
\]
设 \(T=A-B\)。
有 \(T<0\)。
所以，
\[|A-B+D-C|=|T+(D-C)|
\]
\[|A-B+C-D|=|T+(C-D)|
\]
由于 \(|D-C|=|C-D|\)，且 \(D-C>0\)，\(C-D<0\)。
结合 \(T<0\)，有 \(|T+(C-D)|>|T+(D-C)|\)。
排序后 将 0 加入 \(a\) 数组，然后塞到队列里就 OK，每次取队头队尾。
CODE
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxn=6e3;
ll n;
ll ans;
ll a[maxn];
deque<ll>que;
int main()
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
sort(a+1,a+n+1);
ans=1e18;
for(ll k=0;k<=n;k++)
{
ll tmp=k,has=n+k;
ll mx=-1e18,mi=1e18;
for(ll i=1;i<=n;i++)
{
if(a[i]>0)
while(tmp) que.push_back(0),tmp--;
que.push_back(a[i]);
}
while(tmp) que.push_back(0),tmp--;
while(has>1)
{
has-=2;
ll v=que.front()+que.back();
que.pop_front();
que.pop_back();
mx=max(v,mx);
mi=min(v,mi);
}
if(has) mi=min(mi,que.front()),mx=max(mx,que.front()),que.pop_back();
ans=min(ans,mx-mi);
}
printf("%lld",ans);
}
代码比较抽象，看看就好。