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);
}
代码比较抽象,看看就好。
标签:ARC121D,ll,mi,back,que,front,mx From: https://www.cnblogs.com/binbinbjl/p/17883471.html