题意简述

给你一个序列 p1,p2,,pnp_1,p_2,\dots,p_n ,保证序列中的数字不重复且为 11 ~ nn 。你可以选择反转序列中的一个区间(当然也可以不反转),求操作后字典序最小的序列。

题目传送门

思路

首先我们可以检查该序列是否有序,有序(即 pi=ip_i=i)时则已经为字典序最小,则不用反转。

在考虑要反转时的情况。我们找到第一个不有序的位置(即 piip_i \neq i),此时显然 ii 数字一定在 pi+1p_{i + 1} ~ pnp_n 中(设 px=ip_x = i),那为了保证字典序小,只需将 pip_i ~ pxp_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;
}