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