CF1833D题解

DHeasy · 2023-05-20 22:28:04 · 题解

本文章同步发表于博客园

思路

这是一道水题，但细节很多......

首先，要求字典序最大，显然就想到了让最大的数字在第一位。

于是就进一步得出了应该让最大数字在翻转区间的后一位，初步得出了以下思路：

• 找到最大的数（n）所在位置 r，将 r-1；
• 贪心的寻找 r-1 以前第一个比 p_1 小的位置 l；
• 将 l+1；
• 输出区间。

第一个细节

当然，这是有问题的，因为如果 r=n，则也有翻转区间 [n,n] 的可能（参考第 2 个样例）。

所以，当 r=n 时，我们不进行 r-1 这个操作。

第二个细节

但这仍然有问题，如果 r=1 时，翻转区间将是 [l,0]，这个操作是无效的，于是可以想一下，哪个排列开头在不是最大的数时字典序最大呢？

那只能以 n-1（次大的数）作为开头了。

我们就要寻找 n-1 所在位置，再重复以上操作。

参考代码

#include<bits/stdc++.h>
using namespace std;
int t,n,p[2010];
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        int l,r;
        for(int i=1;i<=n;i++){
            scanf("%d",&p[i]);
            if(p[i]==n) r=i;
        }
        if(r==1){
            for(int i=1;i<=n;i++){
                if(p[i]==n-1) r=i;
            }
        }
        if(r!=n) r--;
        l=r;
        for(int i=r-1;i>=1;i--){
            if(p[i]>p[1]) l--;
            else break;
        }
        for(int i=r+1;i<=n;i++) printf("%d ",p[i]);
        for(int i=r;i>=l;i--) printf("%d ",p[i]);
        for(int i=1;i<l;i++) printf("%d ",p[i]);
        putchar('\n');
    }
    return 0;
}