P13021 [GCJ 2021 Qualification] Reversort

题目传送门

思路

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

题意应该不难理解，就是构造一个有

N

个连续正整数的排列嘛，于是就直接放思路了：我们假设当前元素

L_i

是最小的，令

j=i+1

，向后搜一遍找到最小的一个

L_j

，把索引存到

minj

里，然后直接用 reverse 交换数，再把成本计入到

ans

里就行了。

略微解释一下：我们这样换能保证小的数依次被放到前面，且放好的部分不受影响，直到最后一步都不会有多余操作，再看数据范围

2 \le N \le 100

，的确很小，此解法无问题。

代码

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

CPP

#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 代码：

CPP

#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;
}

P13021 [GCJ 2021 Qualification] Reversort

文章操作

题目传送门

思路

代码

相关推荐

评论

P13021 [GCJ 2021 Qualification] Reversort