488 字
2 分钟
CodeForces 2193B: B. Reverse a Permutation
Codeforces
2026-01-29

题目链接#

https://codeforces.com/contest/2193/problem/B

题目大意#

给定条件 给定一个长度为 nn排列 pp(即包含从 11nnnn 个不同整数的数组)。

操作 你可以恰好执行一次以下操作:

  1. 选择一个子区间 [l,r][l, r] (1lrn1 \le l \le r \le n)。
  2. 将该区间内的元素顺序反转

目标 你需要通过这一次操作,使得最终得到的排列在字典序上最大

  • 字典序定义:对于两个排列,从左往右看,在第一个不同的位置上,数值越大的排列字典序越大。

输出 输出操作后得到的那个字典序最大的排列。

解题思路#

看到输出字典序最大,脑子里要立刻想到 贪心 算法。

因为字典序的含义就是要优先保证最高位最大,最高位不是最大的,后面的位数再大也没用,即 2000>19992000 > 1999 的关系。

那么我们的思路就很简单了,因为这是 nn 的排列,所以我们要 找到当前最大的,把他换到当前最高位

  • 即如果 nn 已经在原数组第一位了,那么就要把 n1n-1 换到第二位;
  • 如果 n1n-1 已经在第二位了,那么就继续向下换…………

详情请见代码实现部分的注释。

代码实现#

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int a[N];
int T, n, start, endd;
bool flag;
void solve(){
flag=true;//找到需要换的最大数字就停(因为贪心)
start=0;
endd=0;
scanf("%d", &n);
for(int i=1;i<=n;i++) scanf("%d", &a[i]);
for(int i=1;i<=n;i++) {
if(!flag) break;
if(a[i]==n-i+1) continue;//是不是当前最大的,不是就下一位
else {//不是当前最大的,要换了
start=i;//换的区间的开头
for(int j=i+1;j<=n;j++)
if(a[j]==n-i+1) {//找到哪一个是当前最大的,是末尾
flag=false;
endd=j;
break;
}
}
}
for(int i=1;i<=n;i++) {
if(i>=start&&i<=endd) printf("%d ", a[start+endd-i]);//如果在换的区间中,就倒序输出
else printf("%d ", a[i]);
}
puts("");
}
int main(){
scanf("%d", &T);
while(T--) solve();
return 0;
}
CodeForces 2193B: B. Reverse a Permutation
https://shenyize.com/solutions/codeforces/2193b/
作者
Shenyize
发布于
2026-01-29
许可协议
CC BY-NC-SA 4.0