P13021 [GCJ 2021 Qualification] Reversort

Beautiful_nebula · 2025-07-05 08:18:23 · 题解

题目传送门

思路

注意本题多测，以及输出格式不要弄错。

题意应该不难理解，就是构造一个有 N 个连续正整数的排列嘛，于是就直接放思路了：我们假设当前元素 L_i 是最小的，令 j=i+1，向后搜一遍找到最小的一个 L_j，把索引存到 minj 里，然后直接用 reverse 交换数，再把成本计入到 ans 里就行了。

略微解释一下：我们这样换能保证小的数依次被放到前面，且放好的部分不受影响，直到最后一步都不会有多余操作，再看数据范围 2 \le N \le 100，的确很小，此解法无问题。

代码

其实笔者之前也不常使用 reverse，所以特地用百度 AI 生成了一份模板代码：

#include <iostream>
#include <algorithm> // 包含 std::reverse

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    // 使用 std::reverse 反转数组
    std::reverse(arr, arr + n);

    // 输出反转后的数组
    for(int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

并不难理解吧，括号里填的两个参数分别为数组名和数组名 + 数组长度，类似于 sort 排序，把这个板子套到本题中，就得到了 AC 代码：

#include <iostream>
#include <algorithm>

int L[105], T, N, k;
int main() {
    std::cin >> T;
    while (T--) {
        k += 1;
        std::cin >> N;
        for (int i = 0; i < N; i++) {
            std::cin >> L[i];
        }
        int ans = 0;
        for (int i = 0; i < N - 1; i++) {
            int minj = i;
            for (int j = i + 1; j < N; j++) {
                if(L[j] < L[minj]) minj = j;
            }
            std::reverse(L + i, L + minj + 1);
            ans += minj - i + 1;
        }
        std::cout << "Case #" << k << ": " << ans;
        std::cout << std::endl;
    }
    return 0;
}