題目鏈接
題意：
給出你長度為 n n n的一個序列（n的全排列），讓你通過交換兩個數來讓他變成下標和數值對應，每一場可以包含多對，但是每個點只能用一次，問你最少需要多少場能使得他變成我們需要的序列（單調遞增），并且輸出每次操作的兩個點，
思路：
我們對樣例先進行分析一下來理解題意
4
4 3 2 1
我們可以通過換(4,1),(3，2) {這里指的是數值}
因為沒有一個點使用倆遍，所以我們可以通過一次操作來實作，
然后我們進一步分析，每個位置有兩個屬性分別是：下標和值
這里是一開始的錯誤思路：
一開始以為最多是3場：
那么我們可以其實用正常的思路就是確定一個點兩兩互換
如果我們輸入的是這樣的
2 3 4 5 6 1 那么我們畫出圖形就是圓里是值，外面是下標，線是下標應該對應的值
那么我們很容易想到把1和2互換(代表里面的值)，因為1和2都用過了，所以同一場上不能在換了，我還可以換3和4，5和6換完之后變成，
整理一下就變成這樣的：
那么我們在隨便換一個假如是2和4，那么就會把2歸位 這就是第二場要做的，
第三場要做的就是4和6互換，
但其實這并不是最優的，我們先了解一下這個：
如果
這樣的我們就可以一步互換就可歸位，那么我們就可以盡量將原圖一場歸成這樣的，那么再進行一場就可以將所有歸位，那么我們怎么實作是個問題
還拿上圖來說：
我們要湊對的話，我們發現隔一個交換就可以實作，像我們像構造1和2這一對，我們就交換1和3（里面的值）；
就變成了這樣
3這個地方打個星說明他用過這一場我們不能再用，我們看上一步我們并沒有用到1，但就把1和2湊出來了，那么我們同理把3放中間，交換3兩端的，就可以湊出3和6，剩下4和5自成一對，
這是偶數情況，奇數情況也是這樣的，只不過最后一下會讓獨立出來的一個歸位，
int main() {
n=read;
rep(i,1,n){
a[i]=read;
}
for(int i=1;i<=n;i++){///起點
if(!vis[i]){
int idx=0,tmp=i;
while(!vis[tmp]){
vis[tmp]=1;
b[++idx]=tmp;
tmp=a[tmp];
}
if(idx>=2){
int l=2,r=idx;
while(l<r){
v[1].push_back({b[l],b[r]});
swap(b[l],b[r]);
l++,r--;
}
l=1,r=idx;
while(l<r){
v[2].push_back({b[l],b[r]});
l++,r--;
}
}
}
}
int res=0;
if(v[1].size()) res++;
if(v[2].size()) res++;
printf("%d\n",res);
if(res==0){
return 0;
}
for(int i=1;i<=2;i++){
if(!v[i].size()) continue;
printf("%d ",v[i].size());
for(int j=0;j<v[i].size();j++)
printf("%d %d ",v[i][j].first,v[i][j].second);
puts("");
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277420.html
標籤：其他
上一篇：unity+Vuforia實作用虛擬按鈕進行互動，用手勢控制模型旋轉和縮放
下一篇：Python基礎篇：變數，串列