CF1157F Maximum_Balanced_Circle
题意：
给出一个长度为 \(n\) 的序列 \(a\)，你可以选出序列的任意子集。记这个子集为 \(b\)，大小为 \(k\)，则需要满足 \(\lvert b_i-b_{(i+1)\bmod k}\rvert \le 1\)。你需要最大化 \(k\) 的值，并输出选出的子集 \(b\)。
Solution
注意到最终的集合肯定是形如 $l, l, ···, l + 1, l + 1, ···, r, r, ···, l + 1, l + 1, ···(l, l, ···)$，所以最小值和最大值出现次数一定大于等于 1，中间的数出现次数一定大于等于 2，然后模拟一遍算就行了Code
#include <iostream>
#include <numeric>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int kN = 2e5 + 1;
int n, c[kN], p[kN], l[kN];
pii ans;
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1, x; i <= n; i++) {
cin >> x;
c[x]++;
}
fill(l, l + kN, 1e9);
for (int i = 1; i < kN; i++) {
p[i] = p[i - 1] + c[i];
if (c[i]) {
if (l[i - 1] == 1e9) {
l[i] = i;
} else {
l[i] = l[i - 1];
}
if (!ans.first || p[i] - p[l[i] - 1] > p[ans.second] - p[ans.first - 1]) {
ans = {l[i], i};
}
if (c[i] == 1) {
l[i] = i;
}
}
}
cout << accumulate(c + ans.first, c + ans.second + 1, 0) << '\n';
for (int i = ans.first; i <= ans.second; i++) {
while (c[i] >= 2) {
cout << i << ' ', c[i]--;
}
}
for (int i = ans.second; i >= ans.first; i--) {
while (c[i] >= 1) {
cout << i << ' ', c[i]--;
}
}
return 0;
}