CCF-CSP 202203-2 出行计划 100分 思路讲解

原题链接 CCF-CSP 202203-2 出行计划

1. 暴力枚举 （70分）

• 按照题目要求，给出核酸检测时间q，可以得出核酸报告出具时间q+k
• 对于给出的出行计划，进行遍历即可获得当前检测时间q，能够满足多少出行计划。
• 对于某个给定的出行计划t，c可以知道，要在t时刻能够出行需要满足，当前核酸已出结果，且未过期
• 对于每一个检测时间q，进行循环判断所有的出行计划进行统计即可。

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 4e5 + 10;
int f[N][2];
int n, m, k, q;
int main ( ) {
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        cin >> f[i][0] >> f[i][1];
    }
    for (int i = 0; i < m; ++i) {
        cin >> q;
        int cnt = 0, time = q + k;      // time 为核酸出结果的时间
        for (int j = 0; j < n; ++j) {
            if (time <= f[j][0] && time + f[j][1] - 1 >= f[j][0]) {  // 核酸已经出结果，并且 和核算结果未过期
                ++cnt;
            }
        }
        cout << cnt << endl;
    }
    return 0;
}

2. 差分数组 （100分）

暴力的方式，会有很多重复计算的场景，双重循环会超时，因此可以从区间角度来进行考虑。

• 对于每个出行计划t，c来说，都有一个核酸生成的最早时间和最晚时间。
• 对于q进行核酸检测，则核酸检测有效期间为 [q + k, q + k + c - 1]；
• 因此对于 某个出行时间 t 来说 只要满足 $q+k\le t\le q+k+c-1$ 即可顺利通行
• 对于上式进行转换可以得到 $t-k-c+1\le q\le t-k$， 即做核酸的时间q满足 这种情况则，对于t时刻的出行计划来说，就是满足的。
• 因此对于查分数组 可以考虑在 [t - k - c + 1, t - k] 区间内 次数+1
• 即 f[t - k - c + 1]++, f[t - k + 1] --;

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 4e5 + 10;
int f[N];
int main ( ) {
    int n, m, k, t, c;
    cin >> n >> m >> k;
    for (int i = 0; i < n; ++i) {
        cin >> t >> c;
        // 则 在[l, r] 时间段内做核酸 则此时可以通行
        int l = t - k - c + 1 > 0 ? t - k - c + 1 : 1;
        int r = t - k > 0 ? t - k : 1;
        f[l] += 1;          // 查分数组更新
        f[r + 1] -= 1;
    }
    // 差分数组 预处理
    for (int i = 1; i < N; ++i) { f[i] += f[i - 1]; }
    int q;
    for (int i = 0; i < m; ++i) {
        cin >> q;
        cout << f[q] << endl;           // 直接查询 q 时刻可以通行 的数目
    }
    return 0;
}