Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
给定一个数列{an}，这个数列满足ai≠aj(i≠j)，现在要求你把这个数列从小到大排序，每次允许你交换其中任意一对数，请问最少需要几次交换？【输入格式】
第一行，正整数n (n<=100,000)。 以下若干行，一共n个数，用空格分隔开，表示数列{an},任意-231<ai<231。 <="" p="">
【输出格式】
只有一行，包含一个数，表示最少的交换次数。
Sample Input
8 8 23 4 16 77 -5 53 100
Sample Output
5
【题解】
把所有的数字从小到大排序。
然后记录这个数字它原本的位置在哪里。
比如样例的输入。
最后排序的结果是
-5,4,8,16,23,53,77,100
然后它们原来的位置是
6 3 1 4 2 7 5 8
我们这样。
从第一个元素开始。
它原来的位置是6.
现在6位置上的元素，它原来的位置是7；
而现在7位置上的元素它原来的位置是5；
现在5位置上的元素它原来的位置是2；
现在2位置上的元素它原来的位置是3；
而现在3位置上的元素它原来的位置是1；
至此我们找到了一个循环。如下。
这里的箭头起点元素表示终点元素原来的位置；
那我们可以这样。把原来的无序序列。
位置1和位置6交换。这样满足排序后位置1上的元素来自原来的位置6；
现在6位置上是1位置上的元素。
然后位置6和位置7交换。
这样满足位置6上的元素来自位置7；
然后位置7变成了1位置上的元素。
然后位置7和位置5交换。同样满足了位置7上的元素来自位置5.
然后位置5变成了1位置上的元素。
然后位置2和位置5交换。这样满足了位置5上的元素是来自位置2；
然后位置2变成了1位置上的元素。
然后位置2和位置3交换。因为此时位置2上的元素是1位置上的元素。
所以交换后位置3上的元素上是来自位置1的。而这满足了这个循环节。
然后所需要的交换次数就是箭头的个数。也即节点个数减1；
位置4上的元素还是从位置4来的。无需交换。
【代码】
#include <cstdio>
#include <cstring>
#include <algorithm>
struct data //是结构体的话，会连同pre在排序的时候一起改变
{
int shuju;
int pre;
};
int n;
data a[100001];
__int64 ans = 0;
void input_data()
{
scanf("%d", &n); //输入n个数字
for (int i = 1; i <= n; i++)
scanf("%d", &a[i].shuju), a[i].pre = i;//记录数据同时记录它原本的位置。一开始都在原位
}
int cmp(const data &a, const data &b) //sort函数的比较函数。
{
if (b.shuju > a.shuju)//按照数据的大小升序排序
return 1;
return 0;
}
void get_ans()
{
bool used[100001];
memset(used, false, sizeof(used));//判断之前有没有计算过
for (int i = 1;i <= n;i++)
if (!used[i]) //如果之前没有计算过。
{
int tot = 0;
int k = i;
while (!used[k])//一直找它原来的位置
{
used[k] = true;//同时记录已经计算过。
k = a[k].pre;
tot++;//节点个数递增
}
ans += tot - 1;//按照上面的题解。答案就是节点个数-1(也即边的个数);
}
}
void output_ans()
{
printf("%I64d", ans);//输出答案
}
int main()
{
input_data();
std::sort(a + 1, a + 1 + n, cmp);//没有加using namespace std;就要在前面加std::
get_ans();
output_ans();
return 0;
}