F. Maximum Balanced Circle

题目链接

题意

给出\(n\)个数，现在要从中选出最多的数\(b_i,b_{i+1},\cdots,b_k\)，将这些数连成一个环，要求两两相邻的数相差不超过1。
最后要求输出具体的方案。

题解

一开始想了一个dp，似乎也可以做
这个题也不用这么复杂，因为相差绝对值不超过1，直接统计一下每个数的个数就行了。
因为如果将最后的环给展开，以每个数的值为高，呈现出来的图形一定是先上升后下降的。那么中间部分的数的个数一定大于等于2，最左边和最右边的两个数特殊考虑一下就行了。
代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int n;
int a[N], c[N];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]), c[a[i]]++;
    int ans = 0;
    int l, r;
    int ansl, ansr;
    int sum = 0;
    for(int i = 1; i < N; i++) {
        if(c[i] >= 1 && sum == 0) {
            l = i;
            sum += c[i] ;
        }else if(c[i] > 1) {
            sum += c[i];
        }else if(sum > 0){
            if(c[i] == 1) sum++, r = i;
            else r = i - 1;
            if(sum > ans) {
                ans = sum ;
                ansl = l;
                ansr = r;
            }
            sum = 0;
            if(c[i] == 1) {
                sum++;
                l = i;
            }
        } 
    }
    cout << ans << '\n' ;
    if(c[ansl] == 1) cout << ansl << ' ', ansl++ ;
    for(int i = ansl; i <= ansr; i++) {
        for(int j = 1; j < c[i]; j++) {
            printf("%d ",i) ;
        }
    }
    for(int i = ansr; i >= ansl; i--) {
        printf("%d ",i);
    }
    return 0;
}