P1327 数列排序
- 1.题目
- 2.分析
- 3.代码
- sort + map
- 由于是从后向前遍历，则其实只用更改后面数字的映射
- 4.总结
- 5.更新日志
1.题目
题目描述
给定一个数列 ，这个数列满足 （），现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？
输入格式
第一行是一个整数，代表数字个数 。
第二行有 个整数用空格分隔开，表示数列 。
输出格式
只有一行，包含一个数，表示最少的交换次数。
样例输入 #1
8
8 23 4 16 77 -5 53 100 样例输出 #1
5 提示
数据规模与约定
对于 的数据，保证 ，。
2.分析
将原数组，与排序后的数组比较，遇到数字不同的时候，则找到应该在此位置的数字，并进行交换（最重要的是构造一个映射，便于查找编号）
3.代码
sort + map
#include <iostream>
using namespace std;
#include <algorithm>
#include <map>
const int N = 1e5 + 10;
int a[N], b[N];
map <int, int>mp; //要是开数组的话太大了
//int mp[N];
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
b[i] = a[i];
mp[a[i]] = i; //映射
}
//排好序
sort(b, b + n);
int res = 0;
for (int i = 0; i < n; ++i)
{
if (a[i] != b[i])
{
++res;
//找到应该在i位置的数字的编号
int t = mp[b[i]];
//交换
swap(a[i], a[t]);
//重新编号
mp[a[i]] = i;
mp[a[t]] = t;
}
}
printf("%d\n", res);
return 0;
} 
由于是从后向前遍历，则其实只用更改后面数字的映射
#include <iostream>
using namespace std;
#include <algorithm>
#include <map>
const int N = 1e5 + 10;
int a[N], b[N];
map <int, int>mp;
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
b[i] = a[i];
mp[a[i]] = i; //映射
}
//排好序
sort(b, b + n);
int res = 0;
for (int i = 0; i < n; ++i)
{
if (a[i] != b[i])
{
++res;
//找到应该在i位置的数字的编号
int t = mp[b[i]];
//将i位置的数字放到t位置
a[t] = a[i];
//重新给t位置的数字编号
mp[a[t]] = t;
}
}
printf("%d\n", res);
return 0;
} 