CF1638A Reverse 题解

FFTotoro · 2022-02-15 18:05:56 · 题解

题目要求最终输出字典序最小，可以发现，排在越前面的数越小，字典序也就越小。

我们知道 p_i=i 时字典序为最佳方案。所以，将输入的数值对其下标进行比较，若比下标大，则证明这不是最优方案，以此为交换区间的左端点，找到下标的值在数组中的位置，为右端点，交换这一段，使得 p_i=i，即可将字典序最小化，是最佳选择。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,f=0,f2=0,fl=false,fl2=false; cin>>n;
    vector<int> a(n+1);
    for(int i=1;i<=n;i++){
      cin>>a[i];
      if(a[i]!=i&&!fl){f=i,fl=true;} // 左端点
      else if(!fl2&&fl&&a[i]==f)f2=i,fl2=true; // 右端点
    }
    if(!f&&!f2){
      for(int i=1;i<=n;i++)cout<<a[i]<<' ';
      cout<<endl; continue;
    }
    for(int i=1;i<f;i++)cout<<a[i]<<' ';
    for(int i=0;i<=f2-f;i++)cout<<a[f2-i]<<' '; // 倒序输出
    for(int i=f2+1;i<=n;i++)cout<<a[i]<<' ';
    cout<<endl;
  }
  return 0;
}