题解 CF1311B 【WeirdSort】
ShineEternal
2020-02-26 07:48:26
[更佳的阅读效果。](https://blog.csdn.net/kkkksc03/article/details/104504289)
## description：
- 给定一个长度为 $n$ 的序列 $a_i$。
- 再给定一个长度为 $m$ 的序列 $p_i$。
- 对于每一个 $p_i$，你都可以选择将 $a_{p_i}$ 和 $a_{p_i+1}$ 交换位置，使用次数不限。
- 询问你能否找到一种方案，使得序列满足 $a_1\le a_2\le a_3\le...\le a_n$，输出 `YES` 或 `NO` 即可。
- **多组数据**，数据组数不超过 $100$，$1\le m<n\le 100$，$1\le a_i\le 100$，$1\le p_i< n$。
- translate by @[ShineEternal](https://www.luogu.com.cn/user/45475)。
## solution：
其实我们可以把 $p_i$ 看成一个个传送带。
首先如果有 $m=n-1$，那么任何情况都能传送，也就是说一定有解。
否则的话，我们可以先把传送带排序。
然后这时候传送带可能会有连成一块一块的。（即连续自然数列）
那么同一块的我们可以随便排序，直接 $\operatorname{sort}$ 即可。
每一块传送带都这么操作，最后对 $a$ 数组进行单调性判断。
## code：
```cpp
#include<cstdio>
#include<algorithm>
using namespace std;
int a[105],p[105];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
for(int i=1;i<=m;i++)
{
scanf("%d",&p[i]);
}
sort(p+1,p+m+1);
if(m==n-1)
{
printf("YES\n");
continue;
}
int tmpl=p[1],tmpr=p[1]+1;
for(int i=2;i<=m;i++)
{
if(p[i]>p[i-1]+1)
{
sort(a+tmpl,a+tmpr+1);
tmpl=p[i];
tmpr=p[i]+1;
}
else
{
tmpr++;
}
}
sort(a+tmpl,a+tmpr+1);
int flag=0;
for(int i=2;i<=n;i++)
{
if(a[i]<a[i-1])
{
flag=1;
break;
}
}
if(flag==0)
{
printf("YES\n");
}
else
{
printf("NO\n");
}
}
return 0;
}
```