题意
给你一个1～n的排列。
并给你一个字符串——其中用0和1表示对应数列中的位置上的值可不可以和后面相邻的数交换。
判断该数列能否在限制中交换为不降序数列。
思路
由于刚学了树状数组，一开始以为是用这样的数据结构去找有没有逆序。
事实上题目中的1~n并且每个数并不相同应该引起注意。关键就是这了。
下面是两种不同的思路；
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
//这个思路是只要当前的最大比位子i大，说明要向后移动，要是str=0，则NO；
using namespace std;
int n,a[+];
string str;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
cin>>str;
int maxn=,flag=;
for(int i=;i<=n;i++)
{
if(maxn < a[i])maxn = a[i];
if(str[i-]=='')
{
if(maxn>i)
{
flag=;
break;
}
}
}
if(flag)puts("YES");
else puts("NO");
return ;
}
#include <cstdio>
#include <iostream>
#include <cstring>
#include <string>
//队长是先跑字符串，判断每个i位子的最大可能值；
using namespace std;
int a[],dp[],n;
string str;
int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
}
cin>>str;
dp[n-]=n;
for(int i=n-;i>=;i--)
{
if(str[i]=='')
{
dp[i]=dp[i+];
}
else dp[i]=i+;
}
int flag=;
for(int i=;i<=n;i++)
{
if(a[i]>dp[i-])
{
flag=;
break;
}
}
if(flag)puts("YES");
else puts("NO"); return ;
}