CF 有趣题目做题笔记

SuperSupper / 2024-09-02 / 原文

CF1157F Maximum_Balanced_Circle

Problem

题意：

给出一个长度为 $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;
}