洛谷 P1327 数列排序 代码心得与收获

数列排序

题目描述

给定一个数列 $a$，这个数列满足 $a_i\ne a_j$（$i\ne j$），现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？

输入格式

第一行是一个整数，代表数字个数 $n$。

第二行有 $n$ 个整数用空格分隔开，表示数列 $a$。

输出格式

只有一行，包含一个数，表示最少的交换次数。

样例 #1

样例输入 #1

8
8 23 4 16 77 -5 53 100

样例输出 #1

5

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n\le 10^5$，$-2^{31}<a_i<2^{31}-1$。

#include<iostream>
#include<algorithm>
#include<map>
using namespace std;
int main()
{
	int n,temp,ans = 0;
	cin >> n;
	int* arr1 = new int[n];
	int* arr2 = new int[n];
	map<int, int> list;
	for (int i = 1; i <= n; i++)
	{
		cin >> arr1[i];
		arr2[i] = arr1[i];
		list[arr1[i]] = i;
	}
	sort(arr2 + 1, arr2 + n + 1);//nlogn
	for (int i = 1; i <= n; i++)
	{
		if (arr1[i] != arr2[i])
		{
			ans++;
			/*temp = arr1[i];*/
			//arr1[i] = arr1[list[arr2[i]]];
			//arr1[list[arr2[i]]] = temp;
			temp = list[arr2[i]];
			list[arr1[i]] = temp;
			arr1[temp] = arr1[i];
		}
	}
	cout << ans;
	/*for (int j = 0; j < n; j++)
	{
		cout << arr1[j];
	}*/
	delete[] arr1;
	delete[] arr2;
	return 0;
}

1.本题解使用了map数据结构来记录数据的位置，一个正常的已排序的数组作为模板，我们题目中规定的数组只需要和已排序的数组进行比较即可。如果不一样就和排序好的数组元素进行替换。注意不
2.

temp = list[arr2[i]];
list[arr1[i]] = temp;
arr1[temp] = arr1[i];

代码要注意替换map结构中的数据，要始终保持map保存的是数据对应在arr1中的位置，不然后面会混乱，结构体效果一样。

补充题解中看到的：
快读函数：

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}