HDOJ 5821 Ball (16多校day8 1001)

题目传送门

题意:有n个盒子,每个盒子最多装下一个球。用a[i]表示每个盒子中球的状态。现在给出m个区间,可以在给出的区间任意改变a[i]的顺序。询问能否使a[i]等于b[i]。

题解

看了官方题解才知道是贪心,觉得很巧妙,在此胡口一波。

下标原理

要使a[i]等于b[i],球的颜色是一个很大的干扰。然而,对于同色球而言,(例如有4个全为红色的球),标记为1,2,3,4.从a[i]到b[i]一定存在一种方案,使得这个顺序不发生改变。也就是说,同色球可以处理成若干个不同色球。

对于整个a[i]而言,即有n个不同色球。

贪心的实现

首先,分别将a[i],b[i]标记为1.2.3…n;根据a[i],b[i]球的状态进行sort排序(即是否有球以及球的颜色);

其次,对a[i]重编号:进行逐一对比,若a[i]和b[i]的状态相同,则令c[a[i]标记]=b[i]标记;(c[i]即为a[i]重编号后的标记)

最后,在给出的区间进行sort排序。验证c[i]是否等于b[i],即c[i]是否满足1.2.3…n;

代码

亲测AC

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 100000+10
using namespace std;
int n,m;
int c[N];
pair <int ,int> A[N],B[N];

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);

        for(int i=1;i<=n;++i){
            int x;
            scanf("%d",&x);
            A[i].first=x;
            A[i].second=i; 
        }
        sort(A+1,A+1+n);

        for(int i=1;i<=n;++i){
            int x;
            scanf("%d",&x);
            B[i].first=x;
            B[i].second=i;
        }
        sort(B+1,B+1+n);//将a[i],b[i]编号并排序 

        bool flag=1;
        for(int i=1;i<=n && flag;++i)
            if(A[i].first!=B[i].first) flag=0;
            else c[A[i].second]=B[i].second;

        //将a[i]重编号

        while(m--){
            int x,y;
            scanf("%d%d",&x,&y);
            sort(c+x,c+y+1);
        }//在给定的区间排序 

        for(int i=1;i<=n && flag;++i)
            if(c[i]!=i) flag=0;
        //验证最后的标号是否满足1.2.3...n 

        if(flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

多校渐入尾声,晚上翻了翻各种多校敲的代码,自觉多校虽难但同样受益匪浅。(希望不是最后一次多校啊啊啊)最近想整理多校题,BC,CF代码,写写题解

重新开始写题解,其中一个原因是自己不想把所敲的代码扔的到处都是,最后不知所云;另一个原因是,我最近意识到自己思考题目以及赛后对于题解的利用有问题。我记得我上次问帅副题目,总是问这个算法具体是啥样的啊怎么敲啊,结果帅副说你首先要明白这样做为什么是对的,再去想如何实现。之后想了想,确实有道理。

最后,以上若有不对的地方,欢迎指正。