CF1672F1 Array Shuffling

Alex_Wei · 2022-10-08 19:19:21 · 题解

假设 a 是一个排列，连边 a_i\to b_i。注意到一个环恰好需要环长减 1 步归位，因此答案为 n 减去环的个数，只需保证 a_i\to b_i 形成一个大环即可。

若 a 不是排列，不失一般性地，假定 i 为 a 中出现次数第 i 多的数，其数量为 c_i。类似地，我们发现环的个数至少为 c_1，因为一个环不会经过同一个数两次。进一步地，若存在一个环不经过 1，则必然不优，因为此时图上出现了大于 c_1 个环。

考虑这样一个构造：设 k = \max a_i，则构造环 1\to 2\to\cdots \to k \to 1，然后删去 1\sim k 各一个得到新的环。容易发现若删去 1，则剩余部分不可能有环。

时间复杂度 \mathcal{O}(n\log n)，可以桶排做到线性。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
inline int read() {
  int x = 0;
  char s = getchar();
  while(!isdigit(s)) s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return x;
}
constexpr int N = 2e5 + 5;
int n, a[N], cnt[N];
vector<int> buc[N];
void solve() {
  n = read();
  for(int i = 1; i <= n; i++) cnt[i] = 0, buc[i].clear();
  for(int i = 1; i <= n; i++) buc[++cnt[a[i] = read()]].push_back(i);
  for(int i = 1; i <= n; i++) {
    sort(buc[i].begin(), buc[i].end(), [&](int x, int y) {return a[x] < a[y];});
    for(int j = 1; j < buc[i].size(); j++) swap(a[buc[i][j - 1]], a[buc[i][j]]);
  }
  for(int i = 1; i <= n; i++) cout << a[i] << " ";
  cout << "\n";
}
int main() {
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T;
  cin >> T;
  while(T--) solve();
  return 0;
}