CF1638A Reverse

题意简述

给你一个序列 $p_1,p_2,\dots,p_n$ ,保证序列中的数字不重复且为 $1$ ~ $n$ 。你可以选择反转序列中的一个区间（当然也可以不反转），求操作后字典序最小的序列。

题目传送门

思路

首先我们可以检查该序列是否有序，有序（即 $p_i=i$）时则已经为字典序最小，则不用反转。

在考虑要反转时的情况。我们找到第一个不有序的位置（即 $p_i \neq i$），此时显然 $i$ 数字一定在 $p_{i + 1}$ ~ $p_n$ 中（设 $p_x = i$），那为了保证字典序小，只需将 $p_i$ ~ $p_x$ 反转即可。正确性显然。

参考代码

#include <bits/stdc++.h>
using namespace std;

int T;
int N;
int Num[510];

int main() {
    ios::sync_with_stdio(false);
    cin >> T;
    while(T--) {
        cin >> N;
        for(int i = 1; i <= N; i++) {
            cin >> Num[i];
        }
        for(int i = 1; i <= N; i++) {
            if(Num[i] != i) {
                for(int j = i + 1; j <= N; j++) {
                    if(Num[j] == i) {
                        for(int k = 1; k < i; k++) {
                            cout << Num[k] << " ";
                        }
                        for(int k = j; k >= i; k--) {
                            cout << Num[k] << " ";
                        }
                        for(int k = j + 1; k <= N; k++) {
                            cout << Num[k] << " ";
                        }
                        cout << endl;
                        goto end;
                    }
                }
            }
        }
        for(int i = 1; i <= N; i++) {
            cout << Num[i] << " ";
        }
        cout << endl;
        end:
            continue;
    }
    return 0;
}