题解：P6339 [COCI2007-2008#2] TURBO

· · 题解

解析

本题可以分为4个步骤：

  1. 输入数据。

  2. 交换函数：这个函数接收四个参数：nums 列表、目标数字 t、起始位置 start 和结束位置 end。初始化交换次数 ans 为0，并使用 k 找到目标数字 t 在 nums 列表中的索引。当 k \ne start 时，通过比较 k 和 start 的大小，将 t 向 start 位置交换，更新 k 的位置，并将 ans+1。最终将交换次数 ans 返回。

  3. 主逻辑： 定义 left 和 right 指针，分别指向排列的左右两端，初始化为 0 和 n - 1。turn 变量用于判断当前是奇数阶段还是偶数阶段。当 left \le right 时，根据 turn 的奇偶性，调用 swap_numbers 函数将相应的数字（奇数阶段为 left + 1，偶数阶段为 right + 1）通过交换移到相应位置，并将交换次数添加到 w 列表中。每次操作后，根据阶段更新 left 或 right 指针，并将 turn + 1。

输出结果： 最后，使用 for 循环遍历 w 列表，将每个阶段的交换次数输出。

CODE

n = int(input())
nums = []
for _ in range(n):
    nums.append(int(input()))
def swap_numbers(nums, t, start, end):
    ans = 0
    k = nums.index(t)
    while k!= start:
        if k < start:
            nums[k], nums[k + 1] = nums[k + 1], nums[k]
            k += 1
        else:
            nums[k], nums[k - 1] = nums[k - 1], nums[k]
            k -= 1
        ans += 1
    return ans
w = []
left, right = 0, n - 1
turn = 1
while left <= right:
    if turn % 2 == 1:
        w.append(swap_numbers(nums, left + 1, left, right))
        left += 1
    else:
        w.append(swap_numbers(nums, right + 1, right, left))
        right -= 1
    turn += 1
for res in w:
    print(res)