CSP-202203-2-出行计划

2024-02-12 07:28

文章标签 csp 计划出行 202203

本文主要是介绍CSP-202203-2-出行计划，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

CSP-202203-2-出行计划

【70分思路】

【暴力枚举】还是老样子，直接这样做会时间超限，就不仔细介绍了

#include <iostream>
using namespace std;
int main()
{int n, m, k;cin >> n >> m >> k; int* ti = new int[n];int* ci = new int[n]; for (int i = 0; i < n; i++){cin >> ti[i] >> ci[i];}// 处理查询for (int i = 0; i < m; i++){int t, possibleToPassNum = 0;cin >> t;for (int j = 0; j < n; j++){int earliestEntryTime = t + k, latestEntryTime = t + k + ci[j];if ((earliestEntryTime <= ti[j]) && (ti[j] < latestEntryTime)){possibleToPassNum++;}}cout << possibleToPassNum << endl;}return 0;
}

【100分思路-差分数组和前缀和】

输入处理：
- t表示某人去某地的时间，c表示核酸检测有效期。
- 通过 x = t + 1 - k - c 和 y = t - k 计算符合条件的时间区间 [x, y]。
  - $q + k \leq t ＜ q + k + c$
  - $q + k \leq t \leq q + k + c - 1$
  - 则 $q$ 的范围是： $t + 1 - k - c \leq q \leq t - k$
- 如果 y < 1，说明这个时间区间没有意义，直接跳过，同时保证 1 ≤ x（规定从1开始）
差分数组的处理（重要）：
- 在 x 处加1，表示这个时间点有一个符合条件的出行计划。
- 在 y + 1 处减1，表示这个时间点之后的时间没有符合条件的出行计划。
- 这样通过差分数组，我们记录了每个时间点上的变化。
前缀和计算（重要）：
- 通过遍历整个时间范围，累加差分数组的值，得到每个时间点符合通行条件的计划总数。
- 这一步的目的是恢复出原数组的值，即每个时间点上有多少个符合条件的出行计划。
查询处理：
- 对于每次查询，直接输出对应天数 q 处的计数值，即在查询的天 q 有多少个符合条件的出行计划。

通过这种方式，代码实现了高效处理大规模数据的需求，通过差分数组和前缀和的技巧，避免了对每个查询进行重复的线性遍历，提高了算法的效率。

#include<iostream>
#include<algorithm>
using namespace std;const int N = 2e5 + 10; 
int n, m, k, t, c, q; 
int cnt[N];  // 默认初始化int main() {cin >> n >> m >> k;// 输入每天的核酸检测和有效期，并处理差分数组for (int i = 1; i <= n; i++) {cin >> t >> c;int x = t + 1 - k - c, y = t - k; // 符合条件的时间区间 [x, y]if (y < 1) continue; // y < 1直接跳过（肯定没有任何一个出行符合条件）x = max(1, x);  // x至少为1（规定从1开始）// 在x处加1，y+1处减1，用差分数组记录每个时间点的变化cnt[x]++;cnt[y + 1]--;}// 通过差分数组计算前缀和，即整个时段符合通行条件的数量for (int i = 1; i <= N - 1; i++) {cnt[i] += cnt[i - 1];}// 查询处理while (m--) {cin >> q;// cnt[q]即为满足条件的出行计划总数cout << cnt[q] << endl;}return 0;
}