题目描述: M个人围成一圈,每分钟相邻的两个人可以交换位置(只能有一对交换)。现在给你一个正整数n(0 < n < 1000),求使n个人的顺序颠倒(即每个人左边相邻的人换到右边,右边相邻的人换到左边)所需的最少时间(分钟数)。如:n=4, 输出2.
示例:
输入:n = 4
输出:2
分析:
1人:pass
2人:
- 12
- 21
3人:
- 123
- 213
4人:= 2 + 2
- 1234
- 2134
- 2143
5人: 3 + 2
- 12345
- 12354
- 13254
- 31254
- 32154
不知道各位小伙子懂了没?
根据奇偶来一分为二,因为这是成环的,不需要把 12345 转化成 54321, 变成 32154 就可以了。
然后再讨论一下,把一个数组倒过来,需要多少步,这实际上还是很好算的。自己可以推导一下。
我给一个 递推公式: f[n] = f[n-1] + n-1
代码:
1
2
3
4
5
6
nums = [0, 0, 1, 3]
for i in range(4, 1000):
nums.append(nums[i-1] + i-1)
print(nums[n//2]+nums[n//2] if n % 2 == 0 else nums[n//2] + nums[n//2+1])