题目内容

【CCF-CSP】202203-2. 出行计划

思路分析

方法一：普通法（仅能获得70分）

思路

先将出行计划（进入场所时刻、需要C时刻内的核酸）依次存入数组中，然后根据所查询的做核酸的时刻，依次计算出各个出行计划是否在time_min和time_max的区间内（即核酸有效期），其中：

time_min为出核酸的时刻，等于做核酸的时刻+等待时长
time_max为核酸对于该场所的过期时刻，等于做核酸的时刻+等待时长+C

复杂度

下面分析复杂度。设出行计划、查询个数、等待时间为N，且$$N\in[0, 10^5]$$，则：

存储出行计划需要O(N)
遍历查询并依次比较要两次遍历，因此需要O(N^2)

所以整体的复杂度是O(N^2)，当数据量很大的时候运行会超时，因此只能获得70分。

方法二：差分数组

思路

上层思想：建立一个数组A，存储所有时刻上有多少场所可以进入，这里的时刻指的是出核酸的时刻。

具体实现时，需要计算每个场所对应的可进入时间区间。如计划100时刻去某场所，而该场所要求24小时核酸，说明出核酸的时刻在100-24+1=77到100之间都是能够进入该场所的，那么就需要令A的[77,100]下标内的值都加一。

在实现A内的部分区间统一加一时，如果使用正常的遍历区间内的元素相加，时间复杂度会达到O(N)，因此这里使用了差分数组。

差分数组

差分数组就是一个对应于a[N]的数组b[N]，满足a[i] = b[1] + b[2] + … + b[i]，设置这样的数组后，“部分区间统一加一”的这个操作复杂度就能由O(N)降为O(1)。例如，区间[3,6]统一加一，只需令b[3]+1，b[7]+1，这样a的对应区间就是全部加一的。

复杂度

依然设出行计划、查询个数、等待时间为N，且$$N\in[0, 10^5]$$，则：

遍历出行计划并维护数组A，O(N)
将差分数组整理为正常数组，O(K)，其中$$K=4*10^5+1$$
遍历查询并直接输出结果，O(N)

所以整体复杂度是O(N)，虽然K的值较大，但和庞大的O(N^2)比起来不值一提。

代码

方法一

#include<iostream>
#include<vector>

// 70分

using namespace std;

struct Plan {
    int ptime;
    int interval_require;
};

int main() {
    int plan_num_n, query_num_m, wait_time_k;

    cin >> plan_num_n >> query_num_m >> wait_time_k;

    struct Plan plan;
    vector<struct Plan> plans;
    int queried_time, time_min, time_max;
    int query_result;

    for (int i=0; i<plan_num_n; i++) {
        cin >> plan.ptime >> plan.interval_require;
        plans.push_back(plan);
    }

    for (int i=0; i<query_num_m; i++) {
        query_result = 0;
        cin >> queried_time;
        time_min = queried_time + wait_time_k;
        for(struct Plan plan : plans) {
            if (plan.ptime >= time_min && plan.ptime <= queried_time + \
                    wait_time_k + plan.interval_require - 1) {
                query_result += 1;
            }
        }
        cout << query_result << endl;
    }

    return 0;
}

方法二

#include<iostream>
#include<vector>

// 100分
// 满分题解：https://www.cfanz.cn/mobile/resource/detail/NGMVowMgZLjZJ
// 差分算法：https://www.jianshu.com/p/444096786e49

using namespace std;

const int TIME_NUM_N = 4e5 + 1;
int time2placenum[TIME_NUM_N]; // 差分数组，表示某时刻下可进入场所的个数

// 将数组的[left, right]之间的值都加上value
inline void increase_diff_array(int left, int right, int value) {
    time2placenum[left] += value;
    time2placenum[right + 1] -= value;
}

int main() {
    int plan_num_n, query_num_m, wait_time_k;

    cin >> plan_num_n >> query_num_m >> wait_time_k;

    int place_time_t, interval_c;
    int queried_time, time_min, time_max;

    for (int i=0; i<plan_num_n; i++) {
        cin >> place_time_t >> interval_c;
        time_min = max(place_time_t - interval_c + 1, 1);
        time_max = place_time_t;
        increase_diff_array(time_min, time_max, 1);
    }

    for (int i=1; i<TIME_NUM_N; i++) {
        time2placenum[i] += time2placenum[i-1];
    }

    for (int i=0; i<query_num_m; i++) {
        cin >> queried_time;
        cout << time2placenum[queried_time + wait_time_k] << endl;
    }

    return 0;
}

收获

以前一直觉得算法没卵用，今天这个例子是生活中确实存在的，用一些算法上的例子就能让程序的运行快上不少，证明算法还是有点卵用。

当然，这里假设时间是有限的，现实中可能做不到这样。