思路
这是一道水题,但细节很多......
首先,要求字典序最大,显然就想到了让最大的数字在第一位。
于是就进一步得出了应该让最大数字在翻转区间的后一位,初步得出了以下思路:
- 找到最大的数(\(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
标签:CF1833D,最大,int,题解,--,区间,翻转 From: https://www.cnblogs.com/fengxiaoyi/p/17417930.html