CodeForces 2193B: B. Reverse a Permutation

488 字

2 分钟

CodeForces 2193B: B. Reverse a Permutation

2026-01-29

次阅读

算法

CodeForces

/

算法

题目链接#

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

题目大意#

给定条件 给定一个长度为 $n$ 的排列 $p$ （即包含从 $1$ 到 $n$ 的 $n$ 个不同整数的数组）。

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

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

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

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

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

解题思路#

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

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

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

即如果 $n$ 已经在原数组第一位了，那么就要把 $n-1$ 换到第二位；
如果 $n-1$ 已经在第二位了，那么就继续向下换…………

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

代码实现#

1
#include <bits/stdc++.h>
2
using namespace std;
3
const int N=2e5+10;
4
int a[N];
5
int T, n, start, endd;
6
bool flag;
7
void solve(){
8
  flag=true;//找到需要换的最大数字就停（因为贪心）
9
  start=0;
10
  endd=0;
11
  scanf("%d", &n);
12
  for(int i=1;i<=n;i++) scanf("%d", &a[i]);
13
  for(int i=1;i<=n;i++) {
14
    if(!flag) break;
15
    if(a[i]==n-i+1) continue;//是不是当前最大的，不是就下一位
16
    else {//不是当前最大的，要换了
17
      start=i;//换的区间的开头
18
      for(int j=i+1;j<=n;j++)
19
        if(a[j]==n-i+1)  {//找到哪一个是当前最大的，是末尾
20
          flag=false;
21
          endd=j;
22
          break;
23
        }
24
    }
25
  }
26
  for(int i=1;i<=n;i++) {
27
    if(i>=start&&i<=endd) printf("%d ", a[start+endd-i]);//如果在换的区间中，就倒序输出
28
    else printf("%d ", a[i]);
29
  }
30
  puts("");
31
}
32
int main(){
33
  scanf("%d", &T);
34
  while(T--) solve();
35
  return 0;
36
}