【HDU】5821 Ball

01 Sep 2016

Ball

题目链接

Ball

题目大意

有若干个球装在箱子里，有颜色相同的球也有颜色不同的，颜色相同的球没有区别，现在有对a序列的m个操作，每个操作把从\( l_i \)到\( r_i \)的球重新随机排列，问你经过这些操作后，a序列球的顺序能否和b序列球的顺序相同。

题解

脑洞贪心

这个题比较脑洞。因为颜色相同的球没有区别，我们为了方便处理，把b序列中的球从第一个球最后一个标号1~n，然后在A序列中依次找到相同的球。这样，我们在交换\( l_i \)到\( r_i \)的时候实际上就是把这段区间的数排序，排完序之后和b序列比较就行了。

代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

struct node
{
    int c,p;
    bool operator <(const node &x) const
    {
        return p<x.p;
    }
};
node a[1005];
int T,n,m,b[1005],l,r;

int main()
{
    scanf("%d",&T);
    while (T--)
    {
        memset(a,-1,sizeof(a));
        memset(b,0,sizeof(b));
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++) scanf("%d",&a[i].c);
        for (int i=0;i<n;i++) scanf("%d",&b[i]);
        for (int i=0;i<n;i++)
            for (int j=0;j<n;j++) if (b[i]==a[j].c && a[j].p==-1)
            {
                a[j].p=i;
                break;
            }
        for (int i=0;i<m;i++)
        {
            scanf("%d%d",&l,&r);
            sort(a+l-1,a+r);
        }
        bool flag=0;
        for (int i=0;i<n;i++) if (a[i].c!=b[i])
        {
            flag=1;
            break;
        }
        if (flag) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}