题目大意
题目链接
给定一个序列,这个序列可以理解为一个1~n
的全排列,再给出一个01
串,1
表示可以将索引i
和i+1
进行交换,且交换可以发生任意次,0
表示不可以。
问最后能不能将序列升序排列。
题解
几乎 秒杀,因为简单。
判断每个索引处的数能不能回到自己应该在的位置即可,若都能回去,则输出YES
,反之输出NO
。
当a[i]>i
时,a[i]
应当处于位置i
,判断从位置i
到a[i]-1
是否都可以进行交换,即是否全为1
,若全为1
说明其可以回到应在的位置,反之不可以。
类似的当a[i]<i
时,判断从位置a[i]
到i-1
是否都可以进行交换。
我采用前缀和来判断是否全为1
。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
int a[N], b[N], sum[N], n;
string str;
int main()
{
cin>>n;
for(int i = 1;i <= n;i ++) cin>>a[i];
cin>>str;int len = str.length();
for(int i = 0;i < len;i ++) b[i+1] = str[i] - '0', sum[i+1] = sum[i] + b[i+1];
for(int i = 1;i <= n;i ++) {
if(a[i] > i) {
if(sum[a[i] - 1] - sum[i - 1] == a[i] - i) continue;
else {
puts("NO");
return 0;
}
} else if(a[i] < i) {
if(sum[i - 1] - sum[a[i] - 1] == i - a[i]) continue;
else {
puts("NO");
return 0;
}
}
}
puts("YES");
return 0;
}