Sort with Swap(0,*) (25)

//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;
}

a = list(map(int,input().split()))
i,k,f = 1,0,0
while i <= a[0]:
    if a[i] == i - 1:
        f = 0 if a[1] else 1
        i += 1
    else:
        k += 3 if f else 1
        a[a[i] + 1],a[i] = a[i],a[a[i] + 1]
        f = 0          
print(k)

#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;
}

#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)

ac_code

/*
    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;
}