手机网站开发最好用的框架,网页版传奇开服,怎样找做淘宝客的网站,青浦网络公司网站题目描述
有N个瓶子#xff0c;编号 1 ~ N#xff0c;放在架子上。
比如有5个瓶子#xff1a; 2 1 3 5 4
要求每次拿起2个瓶子#xff0c;交换它们的位置。 经过若干次后#xff0c;使得瓶子的序号为#xff1a; 1 2 3 4 5
对于这么简单的情况#xff0c;显然#…题目描述
有N个瓶子编号 1 ~ N放在架子上。
比如有5个瓶子 2 1 3 5 4
要求每次拿起2个瓶子交换它们的位置。 经过若干次后使得瓶子的序号为 1 2 3 4 5
对于这么简单的情况显然至少需要交换2次就可以复位。
如果瓶子更多呢你可以通过编程来解决。
输入输出
输入格式为两行 第一行: 一个正整数NN10000, 表示瓶子的数目 第二行N个正整数用空格分开表示瓶子目前的排列情况。
输出数据为一行一个正整数表示至少交换多少次才能完成排序。
例如输入 5 3 1 2 5 4
程序应该输出 3
再例如输入 5 5 4 3 2 1
程序应该输出 2
资源约定
峰值内存消耗 256M CPU消耗 3000ms
思路
这题思路很巧妙我们可以将其转化为图论的问题求解。 首先建图因为是1~N的所以将a[i]指向a[a[i]]例如第一个样例。
5
3 1 2 5 4转化成图就行如下所示。 排好之后的图是这样的。 所以我们的目的就是将上面的两个环变成下面的五个环。每次交换两个点其实就是改变了两条边的指向。比如交换3和2就变成了2 1 3 5 4。新图就变成了 其实就是将一个环变成了两个环。每一次这样的交换都会导致上述结果。那么我们最终是要有 n n n 个环。所以我们只需要求出给出的数据有多少环然后让 n n n 减去环的数量就是最少的交换次数。
代码
#include iostream
#include algorithmusing namespace std;const int N 10010;int n;
int a[N];
bool st[N];int main()
{cin n;for ( int i 1; i n; i ) cin a[i];int k 0;for ( int i 1; i n; i )if ( !st[i] ){k ;for ( int j i; !st[j]; j a[j] )st[j] true;}cout n - k endl;return 0;
}
