CSP CCF： 202203-2 出行计划（C++）

文章目录题目来源问题描述问题描述输入格式输出格式样例输入样例输出样例解释子任务解题思路代码题目来源计算机软件能力认证考试系统问题描述试题编号：202203-2试题名称：出行计划时间限制：1.5s内存限制：512.0MB问题描述：问题描述最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。具体来时，如果在t时刻做了核酸检测...

X-omil

7552人浏览 · 2022-04-04 17:29:10

X-omil · 2022-04-04 17:29:10 发布

文章目录

题目来源

计算机软件能力认证考试系统

问题描述

试题编号：	202203-2
试题名称：	出行计划
时间限制：	1.5s
内存限制：	512.0MB
问题描述：	问题描述最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。具体来时，如果在 t 时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要 k 个单位时间，即在 t+k 时刻可以获得结果。如果一个场所要求持 24 个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第 t+k 时刻到第 t+k+23 时刻进入该场所。小 C 按时间顺序列出接下来的 n 项出行计划，其中第 i 项（1≤i≤n）可以概括为： ti 时刻进入某场所，该场所需持有 ci 个单位时间内的核酸检测结果入内，其中 0<ci≤2×105。为了合理安排核酸检测时间，试根据小 C 的出行计划，回答如下查询：如果在 q 时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？这样的查询共有 m 个，分别为 q1,q2,⋯,qm；查询之间互不影响。输入格式输入的第一行包含空格分隔的三个正整数 n、m 和 k，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。接下来输入 n 行，其中每行包含用空格分隔的两个正整数 ti、ci，表示一项出行计划；出行计划按时间顺序给出，满足 0<t1≤t2≤⋯≤tn≤2×105。最后输入 m 行，每行仅包含一个正整数 qi，表示一个查询。m 个查询亦按照时间顺序给出，满足 0<q1<q2<⋯<qm≤2×105。输出格式输出共 m 行，每行一个整数，表示对应查询的答案。样例输入 `6 2 10 5 24 10 24 11 24 34 24 35 24 35 48 1 2` Data 样例输出 `3 3` Data 样例解释时刻 1 做检测，可以满足第三、四、六项出行计划；时刻 2 做检测，可以满足第四、五、六项出行计划。子任务 40% 的测试数据满足 0<n,k≤1000、m=1； 70% 的测试数据满足 0<n,m,k≤1000；全部的测试数据满足 0<n,m,k≤105。

解题思路

q（检测核酸的时刻）的区间

$q_i$ ：检测核酸的时刻

k：检测完核酸等待结果的时间

$t_i$ ：进入到第 i 个出行场所的时刻

$c_i$ ：第 i 个出行场所要求的 $c_i$ 个小时内核酸检测结果

根据题目可知对于每个出行地点都有 $t_i \epsilon [q_j + k, q_j + k + c_i - 1]$ ，可得

$(1) q_j <= t_i - k$

$(2)q_j >= t_i - k - c_i + 1$

根据每个出行地点的 t、c 以及等待核酸结果所需时间 k 就能计算出可以进入该出行地点的核酸检测时刻的左右边界 $t_i - k - c_i + 1$ 、 $t_i - k$ 。

左右边界与 $q_j$ 有如下6 种情况。

第一种情况是左边界< $q_j$ <右边界, 在这种情况下，左边界小于等于 $q_j$ 数量 - 右边界小于 $q_j$ 数量 = 可出行地点数量。

第二种情况是左边界< $q_j$ =右边界, 在这种情况下，左边界小于等于 $q_j$ 数量 - 右边界小于 $q_j$ 数量 = 可出行地点数量。

第三种情况是左边界= $q_j$ <右边界, 在这种情况下，左边界小于等于 $q_j$ 数量 - 右边界小于 $q_j$ 数量 = 可出行地点数量。

第四种情况是左边界<右边界< $q_j$ , 在这种情况下，左边界小于等于 $q_j$ 数量 - 右边界小于 $q_j$ 数量 = 可出行地点数量。

第五种情况是 $q_j$ <左边界<右边界, 在这种情况下，左边界小于等于 $q_j$ 数量 - 右边界小于 $q_j$ 数量 = 可出行地点数量。

第六种情况是左边界= $q_j$ =右边界, 在这种情况下，左边界小于等于 $q_j$ 数量 - 右边界小于 $q_j$ 数量 = 可出行地点数量。

所以对于每个核酸检测时刻 $q_j$ 只需要知道有多少左边界小于等于 $q_j$ 、右边界小于 $q_j$ 的出行场所就可以算出来。

故构建两个数组，一个是左边界数组Qleft，一个是右边界数组Qright。因为右边界是小于 $q_j$ ，所以整个区间应该是左闭右开。

代码

#include <iostream>

using namespace std;

int main()
{
    int n, m, k;
    cin>>n>>m>>k;

    int Qleft[200002] = {0}, Qright[200002] = {0};

    for (int i = 0; i < n; ++i) {
        int t, c;
        cin>>t>>c;
        if (k <= t) {
            int l = max(0, t - c - k + 1);
            int r = t - k + 1;  // 左闭右开
            Qleft[l]++;
            Qright[r]++;
        }
    }

    for (int i = 1; i < 200002; ++i) {  // 是200002！！ 不要写错了
        Qleft[i] += Qleft[i - 1];
        Qright[i] += Qright[i - 1];
    }

    for (int i = 0; i < m; ++i) {
        int q;
        cin>>q;
        int ans = Qleft[q] - Qright[q];
        cout<<ans<<endl;
    }

    return 0;
}

简洁版

#include <iostream>

using namespace std;

int main()
{
    int n, m, k;
    cin>>n>>m>>k;

    int Q[200002] = {0};

    for (int i = 0; i < n; ++i) {
        int t, c;
        cin>>t>>c;
        int l = max(0, t - k - c + 1);
        int r = max(0, t - k);
        ++Q[l];
        --Q[r + 1];
    }

    for (int i = 1; i < 200002; ++i) {
        Q[i] += Q[i - 1];
    }

    for (int i = 0; i < m; ++i) {
        int q;
        cin>>q;

        cout<<Q[q]<<endl;
    }
    return 0;
}

简洁版是参考的：第二十五次csp认证-出行计划_xiaozhou163的博客-CSDN博客