Twist the Permutation 數列的輪換題 Codeforces 776 div3

• 2022 年 3 月 23 日
• 筆記
• brute force, constructive algorithms, Math, OJ 做題題解

這是一道比較經典的將數列中的數字輪換的題目，我們先看題干：

題干分析：先淺淺地分析一下題目是要我們幹什麼，我們會默認有一個已經升序排序地1~n的排列，然後我們會給定一個新排列是在原有排列的基礎上進行operation得到的，那麼我們來看看這個operation是什麼：

  這個operation是對每一個位置i上進行操作的，就是對前i個數向右移動一位，並且在第i位上可以執行的operation次數是無窮的；

  接下來，我們要發現題干叫我們求的是什麼，他問我們能不能從初始序列經過儘可能小的operation次數到達給定的序列，我們就是要讓這個數儘可能地小；

  然後我們是要怎麼解決這道題呢？首先我們可以發現，我是根據i的順序從小到大逐漸把前面的順序逐漸打亂的，說明在d[n]之前，n這個最大的數字肯定是沒有動過，所以d[n]是多少純粹是根據n被移動到了哪裡決定的，因為其他的不影響n的位置，所以可根據n的位置反推出d[n],同理我們可以反推出d[n-1]……以此類推！

  最後我們再來考慮一下是怎麼得到d[n]的，我們通過倒著循環i，當找到n的位置為j之後，我們令ind（index）等於j，我們就知道這裡換轉了（ind+1）%i次

所以我們就把所有的數全部換回去，所以我們循環1~i，找到他們本來的位置換回去，這樣的話，d[n]就完成了，我只要接下來完成同樣的循環就好了！

  因為我需要找回n個數，每次找回一個數的時間複雜度是O（n）的，所以這個演算法的時間複雜度是O（n^2)

   接下來是程式碼：

#include<bits/stdc++.h>

#define maxn 2100

using namespace std;

int q[maxn],n,b[maxn],ans[maxn];

int main()

{

int t;

cin >> t;

while(t–){

int n;

cin >> n;

for(int i = 0;i<n;i++) cin >> q[i];

for(int i = n;i>=1;i–){

int ind  = 0;

for(int j = 0;j<i;j++) ind = q[j]==i ? j : ind;

for(int j = 0;j<i;j++) b[(i+j-1-ind)%i] = q[j];

for(int j = 0;j<i;j++) q[j] = b[j];

ans[i-1] = i!=1 ? (1+ind)%i : 0;

}

for(int i = 0;i<n;i++) cout << ans[i] << ” “;

cout << ‘\n’;

}

return 0;

}