CF1408H Rainbow Triples

· · 题解

请叫我钢铁战神。但是这题实在简单啊，真怪。

首先考虑二分答案，答案显然是有可二分性的。若答案为 k，则我们选的 0 一定是前 k 个和后 k 个，更具体地是第 i 个和倒数第 (k-i+1) 个配对。注意到第 k 个在倒数第 k 个之前，假设出现的非 0 数字互不相同，那么每个数字可以匹配一段前缀或一段后缀。那么考虑一个数字出现多次的情况，其实就是可以匹配一段前缀和一段后缀。现在我们需要判断是否存在完美匹配。考虑反悔贪心，能填就填，填不了了的话我们把能匹配最长后缀的那个踢出来备用。然后再看这些备用的能不能匹配完整个没填的后缀即可。

考虑去掉这个二分答案。首先我们发现无论二分的答案是多少，每个数能匹配的前缀和后缀不会变。也就是说，我能填完的前缀以及能填后缀的备用集合不会变。那我岂不是剩下的后缀越长越好，以免有剩下的。于是直接看在最多的情况下能匹配对少就行。

时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
const int mod=1e9+7;
#define inf 1e9
#define pb push_back
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*f;
}
int n,m,T,L[maxn],R[maxn],a[maxn],tpl,tpr,ans;
vector<int>P[maxn];
priority_queue<int>I,O;
inline void solve(){
    n=read();m=tpl=tpr=ans=0;
    for(int i=1;i<=n;i++)
        a[i]=read(),m+=!a[i];
    m/=2;if(!m)return puts("0"),void();
    for(int i=1;i<=n;i++)L[i]=R[i]=0;
    for(int i=1;i<=n;i++)
        if(!a[i]){++tpl;if(tpl>m)break;}
        else L[a[i]]=tpl;
    for(int i=n;i>=1;i--)
        if(!a[i]){++tpr;if(tpr>m)break;}
        else R[a[i]]=tpr;
    for(int i=0;i<=m;i++)P[i].clear();
    for(int i=1;i<=n;i++)
        if(L[i]||R[i])P[L[i]].pb(R[i]);
    while(!I.empty())I.pop();
    while(!O.empty())O.pop();
    for(auto x:P[0])O.push(-x);
    for(int i=1;i<=m;i++)
        for(auto x:P[i]){
            if(ans<i)I.push(x),++ans;
            else I.push(x),O.push(-I.top()),I.pop();
        }int dt=1;
    while(!O.empty()&&ans+dt<=m){
        int x=-O.top();O.pop();
        if(x>=dt)++dt;
    }printf("%d\n",ans+dt-1);
}
int main(){
    T=read();
    while(T--)solve();
    return 0;
}

深深地感到自己的弱小。