P1327 数列排序

题目描述

给定一个数列{an}，这个数列满足ai≠aj(i≠j)，现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？

输入输出格式

输入格式：

第一行，正整数n (n<=100,000)。

以下若干行，一共n个数，用空格分隔开，表示数列{an},任意-2^31<ai<2^31-1。

输出格式：

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

输入输出样例

输入样例#1：复制

8

8 23 4 16 77 -5 53 100

输出样例#1：复制

思路：贪心。

#include<map>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

map<int,int>id;

int n,ans;

int num[],pos[];

int main(){

    scanf("%d",&n);

    for(int i=;i<=n;i++)    scanf("%d",&num[i]),id[num[i]]=i,pos[i]=num[i];

    sort(pos+,pos++n);

    for(int i=;i<=n;i++)

        if(num[i]!=pos[i]){

            num[id[pos[i]]]=num[i];

            id[num[i]]=id[pos[i]];

            num[i]=pos[i];

            ans++;

        }

    cout<<ans;

}

巴特西

洛谷 P1327 数列排序

P1327 数列排序

题目描述

输入输出格式

输入输出样例

最新文章

热门文章