cf1874A题解

dream10 · 2024-04-22 13:58:30 · 题解

这道题发现了他们贪心的做法就简单，这里补充一下贪心策略证明。

设 A 当前操作方的序列,B 为下次操作方的序列

他们的策略为：如果 Min_A<Max_B 就交换这两个，否则跳过。

然后使用归纳法，设 k 为接下来还要操作的次数，显然 k=1 时这种策略是成立的。k>1时第 2\sim k 次操作也是如此，但是考虑第一次操作是否也要如此。注意：此处只有第一次的策略未确定。

如果交换，设交换了 A_1,B_1 ，如果后面一个人操作的时候没有用到 A_1,B_1 而且根据原题解，后面他们都在交换 MIN,MAX ，不妨使A_1更小，B_1更大。所以将A_1换成它的前驱A_2，知道如果到了更小A_2，就被换回来了，那么也没关系，这说明 A_1<Min_B\leq A_2,如果不换就会让总值变小，换了至少总值没有变化。而且后面的策略是确定的，根据 MIN=A_1 来判断，所以这么选 Min_A 最优，同理选 Max_B。

#include<bits/stdc++.h>
using namespace std;
int t,n,m,k;
int main(){
    cin>>t;
    while(t--){
        cin>>n>>m>>k;
        long long ans=0;
        int minA=2e9,maxB=0,MAX=0,MIN=2e9;
        for(int i=1;i<=n;++i){
            int x;cin>>x;
            minA=min(minA,x);
            MAX=max(MAX,x);
            MIN=min(MIN,x);
            ans+=x;
        }
        for(int i=1;i<=m;++i){
            int x;cin>>x;
            MAX=max(MAX,x);
            MIN=min(MIN,x);
            maxB=max(maxB,x);
        }
        k=(k-1)%2+1;
        if(k>=1)ans+=max(maxB-minA,0);
        if(k>=2){
            ans += MIN-MAX;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

另外如果在 Min_A<Max_B 的时候不交换，相当于错失先机，k--。就算最小值在我这里，最大值在你那里，避免了后面 MIN,MAX 的争夺，但是如果有别的元素，则去除这两个元素，使用归纳法，如果归纳出要的话的证，如果不要的话，则最后一个操作的人得到 MAX，换或不换都可以。

还有 Min_A\geq Max_B 的时候硬要交换。同理，留作思考练习。