Codeforces Round #655 (Div. 2) C

文章目录[x]
  1. 1:题目链接
  2. 2:题面
  3. 3:题意
  4. 4:思路
  5. 5:参考代码




C

题目链接

https://codeforces.com/contest/1372/problem/C

题面

在这里插入图片描述

题意

给定一个长度为的数组,你可以任意选择一个区间使得区间内的数都不在原来位置上,问使该数组从小到大排序,最少经过的次数。

思路

不难想到只有三种情况:

1:原数组本身就是从小到大,答案为,因为不需要排序。
2:记录从左边开始第一个不在自己位置的下标为,从右边边开始第一个不在自己位置的下标为都不在自己的位置上,答案为,因为我们只需要对这部分进行一次排序即可。
3:记录从左边开始第一个不在自己位置的下标为,从右边边开始第一个不在自己位置的下标为存在至少有一个数在自己的位置上,答案为,因为我们只需要对在自己位置上的这部分进行一次排序之后再将[l,r]进行排序即可。

ps:实在不太理解可以把在自己位置的数赋值为,不在自己位置的赋值为,比如"52341 "->"01110",题目要求每个位置都不在原位置,那么你肯定要一次改变连续的"111"的位置然后不管咋样乱序都可以一次变为"11111",这样才是最小次数,又比如:"12435"->"11001",你肯定要一次改变连续的"00"的位置为"11",正确位置,这样才是最小次数。

参考代码

#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
int main() {
  int t, n;
  scanf("%d", &t);
  while (t--) {
    scanf("%d", &n);
    vector<int> ans(n);
    for (auto &a : ans) {
      scanf("%d", &a);
      a--;
    }
    if (is_sorted(ans.begin(), ans.end())) {
      printf("0\n");
    } else {
      int l = 0, r = n;
      while (l < r && ans[l] == l) {
        l++;
      }
      while (r > l && ans[r - 1] == r - 1) {
        r--;
      }
      bool f = 0;
      for (int i = l; i < r; i++) {
        if (ans[i] == i) {
          f = 1;
          break;
        }
      }
      printf("%d\n", f ? 2 : 1);
    }
  }
  return 0;
}


点赞

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像