1127.换位置游戏 题解

题解

题目描述
——————————————————————————————————————————————————————————————————————
N 个小朋友（编号为 1 到 N）正在玩一个换位置游戏。从左到右依次排列着 N 个凳子 （编号为 1 到 N，最左边的为 1 号凳子，最右边的为 N 号凳子），每个凳子上都有一个数字 （凳脚处红色数字），每个数字互不相同，且都是不超过 N 的正整数。

游戏开始前，1 号小朋友坐在 1 号凳子上，2 号小朋友坐在 2 号凳子上，然后依次下去， N 号小朋友坐在 N 号凳子上。

游戏开始后，小朋友看看自己凳子凳脚处的数字，坐到相应的位置上，这是第一轮。

然后又如此仿佛，直到每小朋友坐到了他原来的位置，游戏结束。

问要经过多少轮才结束。

输入
——————————————————————————————————————————————————————————————————————
输入从文件中读取，输入共 2 行。
第 1 行是一个整数 N（1≤N≤1000），表示参加游戏的小朋友人数，当然也表示凳子的 数目。
第 2 行 N 个互不相同的正整数 Ki（1≤Ki≤N，且 1≤i≤N），Ki 表示第 i 把凳子凳脚处的数字。

输出
——————————————————————————————————————————————————————————————————————
结果输出到文件中，输出共 1 行。
表示小朋友们通过换位置后回到游戏开始前坐凳子的状态最少需要经过多少轮。测试数 据保证输出的结果不超出 20000000。

样例输入
——————————————————————————————————————————————————————————————————————
NO.1
3
1 2 3

NO.2
5
2 3 4 5 1

样例输出
——————————————————————————————————————————————————————————————————————
NO.1
1

NO.2
5

数据范围限制
——————————————————————————————————————————————————————————————————————
对于 60%的数据，1≤N≤500，且最少需要交换的轮数不超过 10000。
对于 100%的数据，1≤N≤1000，且最少需要交换的轮数不超过 20000000。

提示
——————————————————————————————————————————————————————————————————————
【样例 1 解释】
输入有 3 把凳子。1 号凳子凳脚处的数字为 1，2 号凳子凳脚处的数字为 2，3 号凳子凳 脚处的数字为 3。第 1 轮换位置后，1 号小朋友仍然坐在 1 号凳子上，2 号小朋友仍然坐在 2 号凳子上，3 号小朋友仍然坐在 3 号凳子上。所以经过 1 轮就回到了游戏开始前状态。
【样例 2 解释】
游戏中有 5 个小朋友 5 把凳子，1 到 5 号凳子凳脚处的数字依次为: 2 3 4 5 1。
第 1 轮换位置后，1 到 5 号凳子上小朋友的编号为：5 1 2 3 4
第 2 轮换位置后，1 到 5 号凳子上小朋友的编号为：4 5 1 2 3
第 3 轮换位置后，1 到 5 号凳子上小朋友的编号为：3 4 5 1 2
第 4 轮换位置后，1 到 5 号凳子上小朋友的编号为：2 3 4 5 1
第 5 轮换位置后，1 到 5 号凳子上小朋友的编号为：1 2 3 4 5

——————————————————————————————————————————————————————————————————————

思路

首先，咱们拟定一个数据
6
3 1 2 5 4 6

根据题意，这题输出为6

怎么得来？

把前三个，第四，五个，第六个划为一个区块

即3 1 2 || 5 4 || 6

第一个区块挪回原来的地方要 3 轮 3
第二个要 2 轮 2
第三个第 1 轮 1

而答案6 = 3*2*1

答案等于乘积吗？

别急这打代码先，再看一个样例

5
1 3 2 5 4
答案为2

先划分区块
1||3 2||5 4

其轮数分别为
1，2，2

答案2

等于什么呢

答案等于最大值吗？

合在一起

最小公倍数
怎么求这个？点我

好了，代码藏在字里行间（超链接），找吧！