P1327 数列排序 题解
sid_shi1
·
2021-06-18 08:13:17
·
题解
题目：P1327 数列排序
思路：
本题可以用一个 map 映射，表示数组中这个值的下标。先拿一个数组当替身，并升序排序，再和原数组进行比较。若值不同，则答案个数加一，然后交换， map 和值都要改。这样子一遍循环就能得出 ans 了，包括前面的 sort 排序，代码总时间复杂度为 O(n log n) ,不会超时。
代码：
#include
using namespace std;
int n,m,a[100001]={0},b[100001]={0},cnt=0;
map
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
a[i]=b[i]=x;//b数组为替身
id[x]=i;//表示原数组中值为x的下表是i
}
sort(b+1,b+n+1);//排序
for(int i=1;i<=n;i++){
if(a[i]!=b[i]){
//交换
a[id[b[i]]]=a[i];
swap(id[a[i]],id[b[i]]);
a[id[b[i]]]=b[i];
//答案加一
cnt++;
}
}
printf("%d",cnt);//输出
return 0;
}