首页 > 其他分享 >ARC121D 1 or 2

ARC121D 1 or 2

时间:2023-12-07 17:22:34浏览次数:39  
标签:ARC121D ll mi back que front mx

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

相关文章

  • 题解 [ARC121D] 1 or 2
    诈骗题,竟然评到了\(2784\)的惊人高分(快到红了),来补个题解。题意:有两个可重集\(A,B\),\(B\)初始为\(\varnothing\)。每次从\(A\)中删除一个或两个数,并将它们的和加入......