2021牛客寒假算法基础集训营2 F. 牛牛与交换排序(思维题、deque)

Description

Solution

数据强度可能不够大，不能保证我的写法是完全正确，不过主要是学会用 模拟实现翻转。
对于本题，我们需要找到一个符合条件的 ，随后利用 实现 的翻转。

找到合适的 ，由限制条件 得到启发，最小的不在自己位置的数字一定是最先处理的。不妨找到第一个不在自己位置的数字 ，令
接下来讲一讲如何实现 模拟区间翻转：

• 维护一个长度为 的双端队列
• 用一个变量记录翻转次数，如果翻转次数为偶数，在前面插入，否则在后面插入
• 使用滑动窗口的思想，如果翻转次数为偶数，要从前面插入，所以弹出队尾的数字，否则弹出队首的数字。
• 最后对于无法翻转的数字再逐一检验。

Code

#include <bits/stdc++.h>
#pragma GCC optimize(3)
typedef long long ll;
using namespace std;

const int N = 4e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;

void solve() {
  int n; cin >> n;
  vector<int> a(n + 1, 0), pos(n + 1, 0);
  for(int i = 1; i <= n; i++) {
    cin >> a[i];
    pos[a[i]] = i; // 记录位置
  }  
  int k = 1, cur = 1; 
  for(int i = 1; i <= n; i++) {
    if(pos[i] != i) {
      k = abs(pos[i] - i) + 1; // 找到k, 第一个不在自己位置的数字
      cur = i;
      break;
    }
  }
  deque<int> q;
  for(int i = cur; i <= cur + k - 1; i++) {
    q.push_back(a[i]);
  }
  int flag = 0; // 判断是放前面还是后面
  for(int i = cur; i + k - 1 <= n; i++) {
    // i + k - 1 <= n 可翻转
    if(q.front() != i && q.back() != i) { // 翻转了也实现不了
      cout << "no\n";
      return ;
    }
    if(!flag && q.front() != i) { // 需要翻转
      flag ^= 1;
    } else if(flag && q.back() != i) { // 需要翻转
      flag ^= 1;
    }
    if(!flag) { // 插入队尾
      q.pop_front();
      if(i + k <= n) {
        q.push_back(a[i + k]);
      }
    } else { // 插入队首
      q.pop_back();
      if(i + k <= n) {
        q.push_front(a[i + k]);
      }
    }
  }
  for(int i = n - k + 2; i <= n; i++) { // 最后对于无法翻转的数字再逐一检验。
    int now;
    if(!flag) {
        now = q.front();
        q.pop_front();
    } else {
        now = q.back();
        q.pop_back();
    }
    if(now != i) {
        cout << "no\n";
        return ;
    }
  }
  cout << "yes\n";
  cout << k << '\n';

}
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
  int T = 1; //cin >> T;
  while(T--) {
    solve();
  }
  return 0;
}