题解 CF1365B 【Trouble Sort】

更佳的阅读效果。

description:

  • 给定一个长度为 $n$ 的序列 $a_i$ 和每个元素的属性 $b_i$。

  • 一次操作定义为一对 $(i,j)$ 满足 $b_i\neq b_j$ 时,交换 $a_i,a_j$。(属性也随之交换)

  • 你需要求出这个序列能否由若干次(可以为 $0$)操作后得到一个不降序列。

  • 输入有多组数据。数据组数不超过 $100$。 $1\le n\le 500$, $1\le a_i\le 10^5$, $b_i\in \{0,1\}$。

  • translate by @ShineEternal

solution:

这道题可以观察到一个十分有趣的属性:只要 $0$ 和 $1$ 都存在,那么这个序列一定能由一些操作后得到不降序列。

否则如果序列最开始已经是不降序列了,也是 Yes

其余情况就是 No 了。

code:

#include<cstdio>
using namespace std;
int a[505],b[505];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        int flag0=0,flag1=0;
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&b[i]);
            if(b[i]==0)
            {
                flag0=1;
            }
            if(b[i]==1)
            {
                flag1=1;
            }
        }
        if(flag0==1&&flag1==1)
        {
            printf("Yes\n");
            continue;
        }
        flag1=0;
        for(int i=2;i<=n;i++)
        {
            if(a[i-1]>a[i])
            {
                printf("No\n");
                flag1=1;
                break;
            }
        }
        if(flag1==0)
        printf("Yes\n");
    }
}

发表于 2020-06-08 20:33:07 in 题解