赛场上思路出来了但是代码没调出来。
首先考虑右端点，很明显，要让操作后的序列字典序尽量地大，那么就要使操作后的序列第一个数尽量地大，考虑 \(n\) 或 \(n-1\)，如果 \(n\) 在原序列的第一个位置，那么此时无论怎么调整都无法使得它在新序列的第一个位置，此时就要考虑让 \(n-1\) 在新序列的第一个位置，和 \(n\) 不在原序列的第一个位置类似，我们只要找到在原序列中的位置，然后 \(r\) 取这个位置的前一个即可。很明显，如果该数在原序列的末尾，那么 \(r\) 就应是 \(n\).
概述着说，就是右端点要找到 \([2,n]\) 中最大的数，若在末尾，则 \(r=n\)，反之 \(r\) 为最大数的前一个数。
接着考虑左端点，我们可以将新序列写成如下形式 \(r+1 \dots n \dots r \dots l \dots 1 \dots l-1\)，那么可以发现，当我们确定了右端点时，\(r+1\dots n\) 这一段就是确定了的，接下来就是要让 \(r \dots l \dots 1 \dots l-1\) 这一段尽量的大。因此我们首先要考虑让 \(l\) 尽量地大，那么很明显，若存在 \(a_i>a_{l-i}\)，那么此时 \(l\) 取 \(i\) 会是更优解。可以画图理解。
时间复杂度将近 \(O(n)\)，通过本题绰绰有余。
#include <cstdio>
#include <iostream>
using namespace std;
int t;
int n;
int a[2005];
int main() {
scanf("%d",&t);
while(t--) {
scanf("%d",&n);
int opt=0;
for(int i=1;i<=n;i++) {
scanf("%d",&a[i]);
if(i>1&&a[i]>a[opt]) opt=i;//寻找[2,n]中最大数所在位置
}
if(n==1) {
printf("%d\n",a[1]);
continue;
}
int l=opt-1;
int r=opt-1;//确定右端点
if(opt==n) l=opt,r=opt;//同上
for(int i=r-1;i>=1;i--) {//寻找最优左端点
if(a[i]>=a[l-i]) l=i;
else break;
}
for(int i=r+1;i<=n;i++) printf("%d ",a[i]);
for(int i=r;i>=l;i--) printf("%d ",a[i]);
for(int i=1;i<=l-1;i++) printf("%d ",a[i]);
printf("\n");
}
return 0;
}