题解 CF1157F 【Maximum Balanced Circle】

2019-06-23 08:14:46


首先,来个桶排序,令 $t_i$ 表示输入序列中 $i$ 出现的次数

然后令 $dp_i$ 表示一个环上最大数为 $i$ 的环的长度

于是,我们开始愉快地分类讨论(其实这只能算递推,不能算dp)

  1. $a_{i-1}=0$ 只能新开一个环, $dp_i=a_i$
  2. $a_{i-1}>1$ 由于 $i-1$ 在环中一定连续(它是当前环中最大值),此时我们可以在构造环时将所有 $i$ 连续地插入 $i-1$ 组成的环的部分内(即插入前环的一部分为 $i-1,i-1,i-1,...,i-1$ 插入后环的一部分为 $i-1,i-1,...,i,i,i,...,i-1$ )

    这样我们就可以保证插入合法, $dp_i=a_i+dp_{i-1}$

  3. $a_{i-1}=1$ ,此时我们可以构造新的环 $C$ , $C_{1..a_i}=i$ 且 $C_{a_i+1}=i-1$ ,此时这个环也是合法的, $dp_i=a_i+1$

同时,递推时用 $start$ 数组记录环的起点,方便输出

输出时就按dp时的构造方法

注意:文字中的 $t$ 数组对应代码中的 $a$

#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n,a[N],dp[N],start[N];
void output(int pos,int top)
{
    for (int i = 1;i < a[pos];i++) printf("%d ",pos);
    if (pos < top) output(pos + 1,top);
    printf("%d ",pos);
}
int main ()
{
    scanf("%d",&n);int tmp,mx = -1;
    for (int i = 1;i <= n;i++) 
        scanf("%d",&tmp),a[tmp]++,mx = max(mx,tmp);
    for (int i = 1;i <= mx;i++)
        if (a[i])
        {
            if (!a[i - 1] || (a[i - 1] == 1 && dp[i - 1] != 1)) 
                dp[i] = a[i] + !!a[i - 1],start[i] = i - !!a[i - 1];
            else 
                dp[i] = a[i] + dp[i - 1],
                start[i] = (start[i - 1] ? start[i - 1] : i);
        }
    int ans = -1,pos = 0;
    for (int i = 1;i <= mx;i++)
        if (dp[i] > ans) {ans = dp[i];pos = i;}
    printf("%d\n",ans);
    if (ans == 1) printf("%d",pos);
    else output(start[pos],pos);
    return 0;
}