思路
这是一道水题，但细节很多......
首先，要求字典序最大，显然就想到了让最大的数字在第一位。
于是就进一步得出了应该让最大数字在翻转区间的后一位，初步得出了以下思路：
- 找到最大的数（\(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;
}
点赞关注一下再走呗qwq