Each input file contains one test case, which gives a positive N (<=105) followed by a permutation sequence of {0, 1, ..., N-1}. All the numbers in a line are separated by a space.
For each case, simply print in a line the minimum number of swaps need to sort the given permutation.
10 3 5 7 2 6 4 9 0 8 1
9
#include<stdio.h> #include<math.h> int main() { int i,j,b=0,c=0,N,a[100000],used[100000]={0}; scanf("%d",&N); for(i=0;i<N;i++)scanf("%d",a+i); for(i=0;i<N;i++){ if(!used[i]){ if(a[i]==i)c++; else for(b++,j=a[i];used[j]=1&&j!=i;j=a[j]); } } printf("%d",N-c+b-2); }
//PAT A1025 #include <iostream> using namespace std; int n, cnt = 0; int a[100005]; int ra[100005]; int Swap(int i, int j) { ++cnt; int temp = a[i]; a[i] = a[j]; a[j] = temp; ra[a[i]] = i; ra[a[j]] = j; return j; }//交换函数中有计数器 int main() { cin >> n; for (int i = 0; i < n; ++i) { cin >> a[i]; ra[a[i]] = i; }//利用reverse_a数组,反向记录a[], //这样的设计可以少写一个search遍历函数,复杂度降低一个线性因子 int zeroPosi = ra[0], m = 0, nOK = 0; for (int i = 0; i < n; ++i) if (a[i] == i)nOK++;//nOK记录已经正确的数字有多少 while (nOK < n) { while (zeroPosi != 0) { zeroPosi = Swap(zeroPosi, ra[zeroPosi]); ++nOK; }++nOK;//a[0]不是0,就一直交换,每一次交换都会使一个数字正确 //直到环路首尾相连a[0]=0,此时环路内所有数字都已正确 //出while时0也就位,故要再一次++nOK if (nOK == n)break;//若全部正确就结束交换 else {//否则任意选择另一环路进入 while (a[m] == m)++m;//这里是从前往后选尚未正确的数字 zeroPosi = Swap(zeroPosi, ra[m]); --nOK;//选择后,该数字作为环路起点,与a[0]的0交换, //因为0离开了位置故执行nOK要减1 } } cout << cnt; return 0; }
#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n, x, answer = 0,num=0; cin >> n; vector<int>number(n); vector<int>reverse(n); for (int i = 0; i < n; i++) { cin>>x; reverse[x] = i; if (x != 0 && x != i) num++;//统计除0外无序的数有多少个 } int k=1; while (num) { int tmp; if (reverse[0] == 0) { for (; k < reverse.size(); k++) { if (reverse[k] != k) { tmp = k; break; } } swap(reverse[0], reverse[tmp]); } else { swap(reverse[0], reverse[reverse[0]]); num--; } answer++; } printf("%d", answer); }
#include <algorithm> #include <iostream> using namespace std; int s[100010]; //数组s用来存下标所在的位置 int main(){ int n,a,num=0,sum=0; //num为除0之外无序的数的个数,sum为共移动的次数 cin>>n; for(int i=0;i<n;i++){ cin>>a; s[a]=i; //数字a所处位置为i if(a!=i&&a!=0) num++; //统计除0外的无序个数 } int k=1; //k为最小的那个无序数 while(num){ if(s[0]==0){ //若0在0号位,则找一个无序数与之交换,使之可以继续每一步就通过交换令一个数有序 for(;k<n;k++){ if(s[k]!=k){ swap(s[0],s[k]); sum++; break; } } } while(s[0]!=0){ //若0不在0号位,将0所在位置的数的当前位置与0的当前位置交换 swap(s[s[0]],s[0]); sum++; num--; } } cout<<sum; return 0; }
#include <iostream> #include <algorithm> #include <memory.h> #include <map> // 没看清题目说明数字为0~N-1 如果给出是自然数也适用 using namespace std; int main(int argc, const char* argv[]) { ios::sync_with_stdio(false); int N, group = 0, swap = 0; cin >> N; int num[100000], sort_num[100000]; bool visit[100000]; // 访问标记 memset(visit, 0, sizeof(bool) * N); for (int i = 0;i < N;i++)cin >> num[i]; memcpy(sort_num, num, sizeof(int) * N); sort(sort_num, sort_num + N); // 对序列排序 map<int, int> m; for (int i = 0;i < N;i++)m[sort_num[i]] = i; // 并记录数值应在的位置 for (int i = 0;i < N;i++) { if (visit[i] || num[i] == sort_num[i])continue; // 如果已被访问或位置正确则跳过 group++; // 环数+1 int j = i; while (!visit[j]) { // 链式访问 visit[j] = true; swap++; j = m[num[j]]; // j转至当前j指向数值该在的位置 } } if (num[0])cout << swap + group - 2; // 若0在某个环中则-2 else cout << swap + group; system("pause"); return 0; }
#include <iostream> #include <memory.h> using namespace std; int main(int argc, const char* argv[]) { ios::sync_with_stdio(false); int N, group = 0, swap = 0; cin >> N; int num[100000]; bool visit[100000]; memset(visit, 0, sizeof(bool) * N); for (int i = 0;i < N;i++)cin >> num[i]; for (int i = 0;i < N;i++) { if (visit[i] || num[i] == i)continue; group++; int j = i; while (!visit[j]) { visit[j] = true; swap++; j = num[j]; } } if (num[0])cout << swap + group - 2; else cout << swap + group; return 0; }
#include <iostream> #include <vector> using namespace std; int main() { ios::sync_with_stdio(false); // 读入数据 int N; cin >> N; vector<int> nums(N, 0); vector<bool> visited(N, false); for(int i=0; i<N; i++) { cin >> nums[i]; } // 处理 // 先计算有0环元素个数 int swaps = 0; int index = 0; visited[index] = true; while(nums[index] != 0) { index = nums[index]; visited[index] = true; swaps++; } // 再计算无0环元素个数 for(int i=1; i<N; i++) { if(visited[i] == false && nums[i] != i) { swaps++; index = i; visited[index] = true; swaps++; while(nums[index] != i) { index = nums[index]; visited[index] = true; swaps++; } } } cout << swaps << endl; return 0; }
#include <iostream> #include <algorithm> using namespace std; int main() { int n,x,cnt=0,sum=0,s[100010]; cin>>n; for(int i=0;i<n;i++) { cin>>x; s[x] = i; if(x!=i && x!=0) cnt++; } int k=1; while(cnt) { if(s[0]==0){ for(;k<n;k++) { if(s[k] != k) { swap(s[0], s[k]); sum++; break; } } } while(s[0]!=0) { swap(s[s[0]], s[0]); sum++; cnt--; } } cout<<sum; return 0; }
//思路:逆向思维,从a[0]开始依次交换,一定能找到0。 //按照题目的意思的话,按我以下思路的反向过程就行了。 // //Order| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | // +---+---+---+---+---+---+---+---+---+---+ // | 3 | 5 | 7 | 2 | 6 | 4 | 9 | 0 | 8 | 1 | // +---+---+---+-—-+---+---+---+---+---+---+ //各回各家,各找各妈。被赶出来的去赶别人。 //a[0] -> a[3] //a[3] -> a[2] //a[2] -> a[7] //a[7] -> a[0] //第一步交换中有0参与,所以次数为3。 //Order| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | // +---+---+---+---+---+---+---+---+---+---+ // | 0 | 5 | 2 | 3 | 6 | 4 | 9 | 7 | 8 | 1 | // +-^-+---+-^-+-—-+---+---+---+-^-+---+---+ //应该的样子: //a[1] -> a[5] 将5放入a[5]中 //a[5] -> a[4] 将4放入a[4]中 //a[4] -> a[6] 将6放入a[6]中 //a[6] -> a[9] 将9放入a[9]中 //a[9] -> a[1] 将1放入a[1]中 //使用0当作中介的样子: //a[0] -> a[1] 将0放入a[1]中 //a[1] -> a[5] 将5放入a[5]中 //a[5] -> a[4] 将4放入a[4]中 //a[4] -> a[6] 将6放入a[6]中 //a[6] -> a[9] 将9放入a[9]中 //a[9] -> a[1] 将1放入a[1]中 //a[1] -> a[0] 将0放入a[0]中 //第二步交换中没有0参与,所以次数为4 + 2 //Order| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | // +---+---+---+---+---+---+---+---+---+---+ // | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | // +-^-+-^-+-^-+-—-+-^-+-^-+-^-+-^-+---+-^-+ //a[3] -> a[3] //第三步无交换,次数为0 //Order| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | // +---+---+---+---+---+---+---+---+---+---+ // | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | // +-^-+-^-+-^-+-^-+-^-+-^-+-^-+-^-+---+-^-+ //a[8] -> a[8] //第四步无交换,次数为0 //Order| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | // +---+---+---+---+---+---+---+---+---+---+ // | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | // +-^-+-^-+-^-+-^-+-^-+-^-+-^-+-^-+-^-+-^-+ //一共9次 #include <stdio.h> #include <cstdlib> #define MY_DEBUG 0 //存放位置 int* numbers; bool* right; int main(int argc, const char *argv[]) { int n, i, j, minCount = 0; scanf("%d", &n); numbers = (int*)malloc(sizeof(int) * n); right = (bool*)malloc(sizeof(bool) * n); for(i = 0 ; i < n ; i++){ scanf("%d", numbers + i); right[i] = false; } for(i = 0 ; i < n ; i++){ if(right[i]) continue; right[i] = true; for(j = numbers[i] ; !right[j] ; j = numbers[j]){ minCount++; right[j] = true; } if(i != 0 && j != numbers[i])//如果该次交换过程中不包含0的话 就加2,为题目要求只能和0交换。 minCount+=2; #if MY_DEBUG == 1 for(j = 0 ; j < n ; j ++) printf("%d", right[j]); printf(" %d \n", minCount); #endif } printf("%d\n", minCount); free(numbers); free(right); return 0; }
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; int n; int main(){ scanf("%d",&n); int a[n]; for(int i = 0 ; i < n; i++){ scanf("%d",&a[i]); } int num = 0; for(int i = 0 ; i < n; i++){ if(a[i] != i){//如果元素没有放对位置 while(a[i] != i){//直到找到该位置对应元素 swap(a[i],a[a[i]]); num += 1; } if(i!=0) num += 2;//第0位有0参与,其他位均多两次交换 } } cout<<num<<endl; }
#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(0); int n,a,step=0; int p[100010]; cin>>n; int left=n-1; for(int i=0; i<n; i++) { cin>>a; p[a]=i; if(p[a]==a&&a!=0) { left--; } } int k=1; while(left>0) { if(p[0]==0) { int i; for(i=k; i<n&&k<n; i++,k++) { if(p[i]!=k) { swap(p[0],p[k]); step++; break; } } } while(p[0]!=0) { swap(p[0],p[p[0]]); left--; step++; } } cout<<step<<endl; return 0; }
// // Created by 江左 on 2021/1/29. // #include <iostream> #include <string> #include <algorithm> #include <vector> #include <map> using namespace std; int main() { int N, Flag, cnt = 0; scanf("%d",&N); int isVisited[100001]={0}; int *arr=new int [N]; for (int i = 0; i < N; ++i) { scanf("%d",&arr[i]); } for (int i = 0; i < N; ++i) { //如果已经被圈过或者就在合适的位置上直接跳过 if(isVisited[arr[i]]==1||arr[i]==i) continue; //下面开始形成圈 Flag=arr[i]; int temp=Flag; bool havaL=false;//有没有0 int num=0; while (true){ num++; if(temp==0) havaL=true; isVisited[temp]=1; temp=arr[temp]; if(temp==Flag){//形成圈了 if(havaL) cnt+=num-1; else cnt+=num+1; break; } } } cout<<cnt; }
#include<iostream> #include<unordered_map> using namespace std; const int N=1e5+10; int a[N]; bool s[N]; unordered_map<int, int> maps; void swaP(int &i,int &j){ cout<<a[i]<<"->"<<a[j]<<endl; int t=maps[a[i]]; maps[a[i]]=maps[a[j]]; maps[a[j]]=t; t=a[i]; a[i]=a[j]; a[j]=t; } int main(){ int n; cin>>n; int res=0; for(int i=0;i<n;i++) { cin>>a[i]; maps[a[i]]=i; } while(1){ if(maps[0]==0){ int m; for(m=1;m<n;m++){ if(maps[m]!=m) { res++; swaP(maps[0],maps[m]); break; } } if(m>=n) break; } else{ s[maps[0]]=true; swaP(maps[0],maps[maps[0]]); res++; } } cout<<res; return 0; }
//Sort with Swap(0, i) (25分) #include <iostream> using namespace std; int n, count = 0; int pos[100000]; int main() { scanf("%d", &n); for (int i = 0; i < n; i++) { int number; scanf("%d", &number); pos[number] = i; } int i = n - 1; while (true) { if (pos[0] == 0) { for (; i >= 0; i--) { if (pos[i] != i) { swap(pos[0], pos[i]); count++; break; } } if (i == -1) break; } else { swap(pos[0], pos[pos[0]]); count++; } } printf("%d", count); }
#include<iostream> using namespace std; int n,total,seq[100005]; void findloop(int t) { int len = 0; while (t != seq[t]) { len++; swap(seq[t], seq[seq[t]]); } total += (t==0 ? len : len + 2); } int main() { cin >> n; for (int i = 0; i < n; i++) cin >> seq[i]; for (int i = 0; i < n; i++) if (i != seq[i]) findloop(i); cout << total; return 0; }
这题不是很难,md我一开始看错题了,思路是对的但是模拟的时候例子是错的,然后发现10是N而不是序列里面的一个元素
我们可以从元素0开始,把当前下标应有的数和0交换,一直这样,直到0回到下标0,然后继续判断是否有不符合条件的数,然后继续交换
原理其实很简单,因为我们保证每一步的交换都是有用的,即让每一个元素回到了自己的本位,这样子得到的结果就是最小的次数(贪心)
#include<bits/stdc++.h> using namespace std; int main() { int n;cin>>n; vector<int> v(n); vector<int> v2(n);//反向索引,O(1),或者用map也行,O(logn) int index;//记录0的位置 int ans=0; for(int i=0;i<n;i++) { cin>>v[i]; if(v[i]==0) index=i; v2[v[i]]=i; } while(index!=0) { swap(v[index],v[v2[index]]); v2[0]=v2[index]; v2[index]=index; index=v2[0]; ans++; } for(int i=0;i<n;i++) { if(v[i]!=i) { v2[v[i]]=index; v2[0]=i; swap(v[index],v[i]); index=v2[0]; ans++; while(index!=0) { swap(v[index],v[v2[index]]); v2[0]=v2[index]; v2[index]=index; index=v2[0]; ans++; } } } cout<<ans<<endl; return 0; }
/*
Sologala @github https://github.com/Sologala/PAT_OJ
PAT_oj No.1067_Sort_with_Swap
*/
思路: 题目让求 用Swap(0, )(*交换数字0和***)来排序最少需要多少次。先来看题目给出的例子。
** B[ ] ={0, 1, 2, 3, 4} 最终排好序
** A[ ] ={4, 0, 2, 1, 3} 在B中对应的是1,所以和A[3]=1交换
Swap(0, 1) => {4, 1, 2, 0, 3} 在B中对应的是3,所以和A[4]=3交换
Swap(0, 3) => {4, 1, 2, 3, 0} 在B中对应的是4,所以和A[0]=4交换
Swap(0, 4) => {0, 1, 2, 3, 4}
我们只需要通过一个hash 表来映射 B的值 与 在A中的下标的关系,就能快速的找到需要交换的两个数。
map add;
但是分析题目给的 眼样例 会出现以下情况
0 1 2 3 4 5 6 7 8 9
3 5 7 2 6 4 9 0 8 1
3 5 0 2 6 4 9 7 8 1
3 5 2 0 6 4 9 7 8 1
0 5 2 3 6 4 9 7 8 1 //
当swap 到如下情况的时候,按照之前的规则0需要交换的是它本身。
因此我们需要找到一个还没有对齐的与之交换,这样就能继续的往下计算。
5 0 2 3 6 4 9 7 8 1 //
而同时我们也可以把找 第一个 没对齐的数字来作为循环出口条件。
while((start=find_first(start))!=-1)
/* Sologala @github https://github.com/Sologala/PAT_OJ PAT_oj No.1067 Sort with Swap */ #include <cstdio> #include <algorithm> #include <vector> #include <map> using namespace std; map<int,int> add; vector<int> A,B; int find_first(int start){ for(int i=start;i<A.size();i++){ if(A[i]!=B[i]) return i; } return -1; } int main(){ int cnt,zero_add; scanf("%d",&cnt); A.resize(cnt); for(int i = 0; i < cnt; i++) { scanf("%d",&A[i]); if(A[i]==0){ zero_add =i; } add[A[i]]=i;//建立地址映射 } B = A;//拷贝一份排好序 作为参照 sort(B.begin(),B.end()); int i=zero_add,count=0,start =0; while((start=find_first(start))!=-1){//find_first找第一个没有对齐的下标 int swap_add =add[B[i]]; //如果没有 返回-1,作为循环出口 if(A[i]==B[i]){//处理 在对齐过程中 0先对齐的情况。 add[A[i]] =start; add[A[start]] =i; swap(A[i],A[start]); count++; i =start; swap_add =add[B[i]]; } else{ swap(A[i],A[swap_add]); i =swap_add; count++; } } printf("%d\n",count); return 0; }
PAT不超时
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 100010;
int n, noindex = 0;
int hashtable[maxn] = {0};
int main() {
int temp, step = 0;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d", &temp);
hashtable[temp] = i;
}
while (true) {
while (hashtable[0] != 0) {
swap(hashtable[0], hashtable[hashtable[0]]);
step++;
}
while (noindex == hashtable[noindex] && noindex < n) {
noindex++;
}
if (noindex == n) break;
swap(hashtable[noindex], hashtable[0]);
step++;
}
printf("%d", step);
return 0;
}