題意
給一個n個數的數列a，a[i]<=n
定義一個操作：每次可以交換任意位置的兩個值；
定義最優操作:對于任意一個原數列的一組排列，使其通過盡可能少的操作變回原數列；
求構造一組原數列的一組排列，使得在最優操作下操作次數盡可能多；
一開始讀錯題了，讀成只能交換相鄰點，一直在考慮逆序對，終于寫出來了以后，一直wa，才發現原來是任意點交換，哭
提示
1. 考慮每個點的值沒有重復的話，那么很簡單，直接構建一個環就好了，操作次數N-1
2. 考慮到有兩個相同數值的在一個環里的話，那么就可以分裂成兩個環，這樣最優解的個數就能減一
3. 因此只需要每次構建一個環，把所有數值的點每次囊括進去一個，直到沒有環就好了
代碼
#include<bits/stdc++.h>
using namespace std;
vector<int> G[200005];
int a[200005], b[200005];
void run() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
G[i].clear();
}
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a[i] = x;
G[x].emplace_back(i);
}
set<int> cnt;
for (int i = 1; i <= n; i++) {
if (G[i].size())cnt.emplace(i);
}
int sum = 0;
while (sum < n) {
vector<int> now, u;
for (auto k: cnt) {
now.emplace_back(G[k].back());
G[k].pop_back();
if (G[k].size() == 0) {
u.emplace_back(k);
}
}
sum += now.size();
for (int i = 0; i < now.size() - 1; i++) {
b[now[i + 1]] = a[now[i]];
}
b[now[0]] = a[now[now.size() - 1]];
for (auto k: u)cnt.erase(k);
}
for (int i = 1; i <= n; i++)cout << b[i] << " \n"[i == n];
}
int main() {
int t;
cin >> t;
while (t--)
run();
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/519300.html
標籤：其他
上一篇：模糊測驗工具AFL原始碼淺析
下一篇：全球名校AI課程庫（24） | MIT麻省理工 · 計算機科學與Python編程導論課程『Introduction to Computer Science and Programming』