CF920C

kirky_wang · 2022-08-05 15:26:04 · 题解

题意：

给一串数字序列和一串 01 组成的字符串。如果数字序列中的元素所在下标在字符串中为 1，则可以和 i-1 交换。求是否可以得到递增的数字序列。

思路：

根据冒泡排序定义可知，任何一个无序序列都可以通过相邻元素交换变成有序的。那么问题就简单了。 如果当前数字不能交换，则判断它是否等于其下标 +1。 否则判断找出这一段 1 的右边界（0 或 \backslash 0），判断这一段区间内存储的数字是否在下标区间内。如果在区间外则输出 no。将 j 的值赋 i。

可以定义一个 vmin，vmax 记录区间内的最大值和最小值。事实上，为了节省时间，可以省略 vmin，因为已知左边界，所以在遍历数组时判断当前下标的数字是否小于左边界就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
int n,a[200005];
char str[200005];
int main(){
    cin>>n;
    memset(str,0,sizeof(str));
    for(int i = 0; i < n; i++)
        cin>>a[i];
    cin>>str;
    int i,j;
    for(i = 0; i < n; i++){
       if(str[i] == '1'){//如果是1可交换，一直往后到0第一个不可交换的数或字符串结束为止
          int vmax = 0;//记录可交换区间内最大数
          for(j = i; ; j++){
             if(a[j] < i+1){//小于左边界说明不在区间内不符合
                printf("NO\n");
                return 0;
             }
             vmax = max(vmax,a[j]);
             if(str[j] == '0' || str[j] == 0){
                if(vmax > j+1){//如果到了右边界，且区间内的最大值超出右边界不符合
                    printf("NO\n");
                    return 0;
                }
                i = j;
                break;
             }
          }
       }
       else if(a[i] != i+1){//如果是0不可交换，那么这个数必须等于下标+1，否则不对
          printf("NO\n");
          return 0;
       }
    }
    printf("YES\n");
    return 0;
}