NYOJ -1364 （第十一届河南省赛）

太过爱你忘了你带给我的痛 2022-02-19 09:13 112阅读 0赞

题目衔接： [http://acm.nyist.cf/problem/1364][http_acm.nyist.cf_problem_1364]

> # 治安管理 #
> 
>  
> 
>  *  内存限制:128MB 时间限制:3000ms 特判: No
> 
>  *    
>     
>  *  通过数:51 提交数:132 难度:2
> 
>   
> 
> 
> ## 题目描述: ##
> 
> SZ市是中国改革开放建立的经济特区，是中国改革开放的窗口，已发展为有一定影响力的国际化城市，创造了举世瞩目的“SZ速度”。SZ市海、陆、空、铁口岸俱全，是中国拥有口岸数量最多、出入境人员最多、车流量最大的口岸城市.   
> 为了维护SZ经济特区社会治安秩序，保障特区改革开放和经济建设的顺利进行, 特别设立了SZ社会治安综合治理委员会主管特区的社会治安综合治理工作。公安机关是社会治安的主管部门，依照法律、法规的规定进行治安行政管理，打击扰乱社会治安的违法犯罪行为，维护社会秩序。  
> YYH大型活动将在\[S,F）这段时间举行，现要求活动期间任何时刻巡逻的警察人数不少于M人。公安机关将有N名警察在维护活动的安全，每人巡逻时间为\[ai,bi)。请你检查目前的值班安排，是否符合要求。若满足要求，输出YES，并输出某个时刻同时巡逻的最多人数；若不满足要求，输出NO，并输出某个时刻同时巡逻的最少人数。
> 
>  
> 
> ## 输入描述: ##
> 
>     第一行： T 表示以下有T组测试数据（ 1≤ T ≤5 ）
>     
>     对每组数据，   
>     
>     第一行：N  M  S  F        ( 1≤N≤10000  1≤M ≤1000  0≤S<F≤100000）
>     
>     第二行，a1  a2 ….  an     警察巡逻起始时间  
>     
>     第三行，b1  b2 ….  bn     警察巡逻结束时间     (  0≤ai0  i=1…. n）
> 
> ## 输出描述: ##
> 
>     对每组测试数据，输出占一行。若满足要求，输出YES，并输出某个时刻同时巡逻的最多人数；若不满足要求，输出NO，并输出某个时刻同时巡逻的最少人数。（中间一个空格）
> 
> # #

>  
> 
> ## 样例输入: ##
> 
>     2
>     5 2 0 10
>     0 0 2 7 6
>     6 2 7 10 10
>     10 2 6 11
>     1 3 5 7 9 2 4 6 8 10
>     2 4 6 8 10 3 5 7 9 11
> 
> ## 样例输出: ##
> 
>     YES 2
>     NO 1

题目大意：。。。

思路：大水题，直接类似于桶排，找下区间内最大最小值即可，但是要注意区间是左开右闭！！！！wa了好几发才看到。

代码：

/*
    题目大意
    */
    #include<map>
    #include<set>
    #include <vector>
    #include<stack>
    #include<queue>
    #include<cmath>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define ll unsigned long long
    #define inf 0x3f3f3f
    #define esp 1e-8
    #define bug {printf("mmp\n");}
    #define mm(a,b) memset(a,b,sizeof(a))
    #define T() int test,q=1;scanf("%d",&test); while(test--)
    #define Test() {freopen("F:\\B.in","r",stdin);freopen("F:\\test2.out","w",stdout);}
    const int maxn=1e5+10;
    const double pi=acos(-1.0);
    const int N=110;
    const ll mod=1e9+7;
    
    
    int num[maxn];
    int a[maxn],b[maxn];
    
    
    int main()
    {
        T()
        {
            mm(num,0);
            mm(a,0);
            mm(b,0);
            int n,m,s,f;
            cin>>n>>m>>s>>f;
            for(int i=0; i<n; i++)
            {
                cin>>a[i];
            }
            for(int i=0; i<n; i++)
            {
                cin>>b[i];
                for(int j=a[i]; j<b[i]; j++)
                {
                    num[j]++;
                }
            }
            int flag=0,minn=inf,maxx=-inf,id1,id2;
            for(int i=s; i<f; i++)
            {
                if(minn>num[i])
                {
                    minn=num[i];
                }
                if(maxx<num[i])
                {
                    maxx=num[i];
                }
            }
            if(minn<m)
                cout<<"NO "<<minn<<endl;
            else
                cout<<"YES "<<maxx<<endl;
        }
        return 0;
    }

[http_acm.nyist.cf_problem_1364]: http://acm.nyist.cf/problem/1364