2022NHOI小甲第五题 幸福时刻3（2.7）

Question

题目描述
小明跟他的小朋友们共n人商量在保证做完的前提下出去玩。第i个小朋友可以玩耍的时间是SiTi。这里SiTi表示的是时间段，比如Si=2,Ti=4，那么意味着这位小朋友在时刻1不能玩，时刻2、3、4可以去玩，时刻4以后都不能出去玩。如果在某个时刻，在一起玩的小朋友个数不少于k个，那么这一时刻就是幸福的。现在你要求出小朋友共有多少个时刻是幸福的。
输入
第一行：n k （n个小朋友，一起玩的小朋友达到k个为幸福）
第二行：S1 S2 ... Sn
第三行：T1 T2 ... Tn

输出
输出一行：幸福时刻数

样例输入 复制
4 3
1 2 2 4
5 2 4 6
样例输出 复制
2
第2分钟和第4分钟一起玩耍的小朋友达到了3个所以是幸福的时刻，幸福时刻数2。
【数据规模】
对于50%的数据 n≤1000 1≤Si≤Ti≤1000
对于100%的数据 n≤100000 1≤Si≤Ti≤1000000000

来源/分类
结构体 前缀和 分段操作

Answer 1

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 定义一个结构体，表示小朋友的开始和结束时间
struct Child {
    int start; // 开始时间
    int end; // 结束时间
};

// 定义一个比较函数，按照结束时间从小到大排序
bool cmp(Child a, Child b) {
    return a.end < b.end;
}

// 定义一个函数，计算幸福时刻数
int happyTime(vector<Child>& children, int k) {
    // 对小朋友的时间段进行排序
    sort(children.begin(), children.end(), cmp);
    // 初始化幸福时刻数为0
    int ans = 0;
    // 初始化当前时刻为0
    int cur = 0;
    // 初始化当前玩耍的小朋友数为0
    int cnt = 0;
    // 遍历所有的小朋友
    for (int i = 0; i < children.size(); i++) {
        // 如果当前时刻小于小朋友的开始时间，说明没有小朋友可以玩
        if (cur < children[i].start) {
            // 更新当前时刻为小朋友的开始时间
            cur = children[i].start;
            // 更新当前玩耍的小朋友数为1
            cnt = 1;
        }
        // 否则，说明当前时刻有小朋友可以玩
        else {
            // 更新当前玩耍的小朋友数加1
            cnt++;
        }
        // 如果当前玩耍的小朋友数不少于k，说明当前时刻是幸福的
        if (cnt >= k) {
            // 更新幸福时刻数加1
            ans++;
        }
        // 更新当前时刻为小朋友的结束时间加1
        cur = children[i].end + 1;
    }
    // 返回幸福时刻数
    return ans;
}

// 主函数
int main() {
    // 输入n和k
    int n, k;
    cin >> n >> k;
    // 定义一个向量，存储所有的小朋友
    vector<Child> children(n);
    // 输入所有小朋友的开始和结束时间
    for (int i = 0; i < n; i++) {
        cin >> children[i].start;
    }
    for (int i = 0; i < n; i++) {
        cin >> children[i].end;
    }
    // 调用函数，计算幸福时刻数
    int ans = happyTime(children, k);
    // 输出结果
    cout << ans << endl;
    // 返回0
    return 0;
}