「Codeforces」A. Reverse-Toy模板网

这篇具有很好参考价值的文章主要介绍了「Codeforces」A. Reverse。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A. Reverse

2022年2月15日15:29:19

题目描述

给一个长度为 n 序列， $p_1, p_2, \dots, p_n$ 。选择两个整数，即一个区间 $[L, R]$ ，对其区间进行反转操作。

要求你找到恰好执行一次反转操作获得的字典最小序列。

序列是一个数组，由 1 到 n 以内的不同数字任意顺序排列组成。例如 $[2, 3, 1, 5, 4]$ 是一个排列，但 $[1, 2, 2]$ 和 $[1, 3, 4]$ 不是，前者是因为数字重复，后者是因为最大值超过了 n（不在 n 范围内）。

输入描述

第一行 T（ $1 <= t <= 500$ ）表示测试样例数量，每组测试样例描述如下：

每组测试用例的第一行包含一个整数 n（ $1 <= n <= 500$ ），表示序列长度。

每组测试用例的第二行包含 n 个整数，表示序列元素。

输出描述

输出可以获得的字典序最小的排列

样例

#1

提示

解析

找到第一个 $A [i]! = i$ 的元素下标为 L，接着找 $A [i] == t$ 的元素下标 R，对这个 $[L, R]$ 区间进行反转即可。文章来源地址https://www.toymoban.com/news/detail-433896.html

AC Code

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st = new StreamTokenizer(br);
    static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

    public static void main(String[] args) throws Exception {
        int T = nextInt();
        while(T != 0) {
            int n = nextInt();
            int[] A = new int[n+1];
            for(int i = 1; i <= n; i++) A[i] = nextInt();
            int L = 0, R = 0;
            for(int i = 1; i <= n; i++) {
                if(L == 0 && A[i] != i) {
                    L = i;
                    continue;
                }
                if(L != 0 && A[i] == L) {
                    R = i;
                    break;
                }
            }
            A = reverse(A, L, R, n);
            for(int i = 1; i <= n; i++) out.print(A[i] + " ");
            out.println();
            T--;
        }
        out.flush();
    }

    public static int[] reverse(int[] arr, int start, int end, int n) {
        int[] A = new int[n+1];
        int cnt = start;
        while(start <= end) A[cnt++] = arr[end--];
        for(int i = 1; i <= n; i++) {
            if(A[i] == 0) A[i] = arr[i];
        }
        return A;
    }

    public static int nextInt() throws Exception {
        st.nextToken();
        return (int) st.nval;
    }
}