[CF1157F] Maximum Balanced Circle

Description

输入 (n) 个数,构造一个最大的环，环上任意 ( extrm{abs}(a[(i+1)\%n]-a[i]) le 1)。(a_i le 2 imes 10^5)

Solution

一定要找一段 (l,l+1,l+2,...,r)，其中除了 (l,r) 可以只出现一次以外，其它的都至少要出现两次

考虑到 (a_i le 2 imes 10^5)，用桶处理一下即可

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1000005;

int n,a[N+5],s[N+5],ans,p,q;

signed main() {
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++) {
        int x=0;
        cin>>x;
        a[x]++;
    }
    for(int i=1;i<=N;i++) {
        s[i]=s[i-1]+a[i];
    }
    int i=1,j=1;
    while(i<N) {
        if(a[i]==0) {
            ++i;
            continue;
        }
        j=i;
        while(j<N && a[j+1]>1 && a[j+2]) ++j;
        if(a[j+1]) ++j;
        ans=max(ans,s[j]-s[i-1]);
        if(ans==s[j]-s[i-1]) {
            p=i;
            q=j;
        }
        i=max(i+1,j);
    }
    cout<<ans<<endl;
    for(int i=p;i<=q;i++) --a[i],cout<<i<<" ";
    for(int i=q;i>=p;--i) while(a[i]) --a[i], cout<<i<<" ";
}