题解 CF1157F 【Maximum Balanced Circle】

首先，来个桶排序，令$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$ ```cpp #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; } ```