题目链接:http://nyoj.top/problem/1364

  • 内存限制:128MB 时间限制:3000ms 特判: No

题目描述

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

解题思路

题意:给你每个保安的开始和结束的巡逻时间，判断s~f这个时间段的人数是不是都不少于m。
思路:直接求出每个时间点的人数，判断一下就行了。

#include <bits/stdc++.h>
using namespace std;
int p[100005];
int main() {
    int t, n, m, s, f, a, b, max_, min_, temp;
    scanf("%d", &t);
    while (t--) {
        temp = 1;
        max_ = 0;
        min_ = 0x3f3f3f3f;
        memset(p, 0, sizeof(p));
        scanf("%d%d%d%d", &n, &m, &s, &f);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a);
            p[a]++;
        }
        for (int i = 0; i < n; i++) {
            scanf("%d", &b);
            p[b]--;
        }
        for (int i = 1; i < f; i++)
            p[i] += p[i - 1];
        for (int i = s; i < f; i++) {
            if (p[i] < m)
                temp = 0;
            max_ = max(max_, p[i]);
            min_ = min(min_, p[i]);
        }
        if (temp)
            printf("YES %d\n", max_);
        else printf("NO %d\n", min_);
    }
    return 0;
}