Phoenix and Socks

Light_snow · 2021-05-03 20:57:09 · 题解

本文同步自link。

看出来如果 l,r 不相等，则一定要从多的一边向少的一边转变，那么这个时候尽量让能匹配的袜子多就行了，即把多的一边的多出来的同色袜子移到另一边。

最后统计答案统计为需要更改的袜子，以及还未配对的袜子的数目的一半。

// code by fhq_treap
#include<bits/stdc++.h>
#define ll long long
#define N 300005

inline ll read(){
    char C=getchar();
    ll A=0 , F=1;
    while(('0' > C || C > '9') && (C != '-')) C=getchar();
    if(C == '-') F=-1 , C=getchar();
    while('0' <= C && C <= '9') A=(A << 1)+(A << 3)+(C - 48) , C=getchar();
    return A*F;
}

struct P{
    int to,next;
};

struct Map{
    P e[N << 1];
    int head[N],cnt;
    Map(){
        std::memset(head,0,sizeof(head));
        cnt = 0;
    }
    inline void add(int x,int y){
        e[++cnt].to = y;
        e[cnt].next = head[x];
        head[x] = cnt;
    }
};

ll t,n,l,r;
ll c[N],lc[N],rc[N],cnt[N];
bool del[N];

int main(){
    t = read();
    while(t -- ){
        n = read(),l = read(),r = read();
        for(int i = 1;i <= n;++i)
        c[i] = read(),lc[c[i]] = 0,rc[c[i]] = 0,cnt[c[i]] = 0,del[c[i]] = 0;
        for(int i = 1;i <= l;++i)
        lc[c[i]] ++ ,cnt[c[i]] ++ ;
        for(int i = l + 1;i <= n;++i)
        rc[c[i]] ++ ,cnt[c[i]] ++ ;
        for(int i = 1;i <= l;++i)
        if(rc[c[i]])
        rc[c[i]] -- ,lc[c[i]] -- ,cnt[c[i]] -= 2;
        ll need = abs(r - l) / 2;
        if(l > r){
            for(int i = 1;i <= l;++i){
                while(need && lc[c[i]] >= 2)
                lc[c[i]] -= 2,cnt[c[i]] -= 2,need -- ;
            }
        }else{
            if(l < r){
                for(int i = l + 1;i <= n;++i)
                while(need && rc[c[i]] >= 2)
                rc[c[i]] -= 2,cnt[c[i]] -= 2,need -- ;
            }
        }
        ll ans = 0;
        for(int i = 1;i <= n;++i){
            if(!del[c[i]])
            del[c[i]] = 1,ans += cnt[c[i]] ;
        }
        std::cout<<ans / 2 + abs(r - l) / 2<<std::endl;
    }
}