本文主要是介绍【CSP：202203-2】出行计划（Java），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接
- 202203-2 出行计划
题目描述
求解思路
- 差分：测试数据中的 n n n， m m m 取值都比较大，直接暴力模拟的话会超时。因此我们在初始化出一个数组，根据做核酸的时间来对应可以出行的行程数量。
res[i]表示在i时刻做核酸可以出行的行程数。- 对于在 q q q 时刻做的核酸，根据题意应该满足 q + k ≤ t i q+k \leq t_i q+k≤ti 并且 t i − ( q + k ) < c i t_i-(q+k) < c_i ti−(q+k)<ci。那么对于第 i i i 个行程，做核酸的有效时间为 q ∈ ( t i − k − c i , t i − k ] q \in (t_i-k-c_i, t_i-k] q∈(ti−k−ci,ti−k]，即 q ∈ [ t i − k − c i + 1 , t i − k ] q \in [t_i-k-c_i+1, t_i-k] q∈[ti−k−ci+1,ti−k]。
- 那么我们每读取一个行程，就对其进行处理。找到其左右边界进行差分。让在 [ l , r ] [l, r] [l,r] 时间段内能出行的计划个数加一。最后让数组
res求前缀和即可。
实现代码
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();int k = in.nextInt();int[] res = new int[200010];for (int i = 0; i < n; i++) {int t = in.nextInt();int c = in.nextInt();// 在[l. r]区间内做核酸可以进入int l = Math.max(t - k - c + 1, 0);int r = Math.max(0, t - k);// 差分：在[l, r]时间段内能出行的计划个数加一res[l] ++;res[r + 1] --;}// 求前缀和for (int i = 1; i <= 200000; i++) {res[i] += res[i - 1];}for (int i = 0; i < m; i++) {int q = in.nextInt();System.out.println(res[q]);}}
}
这篇关于【CSP：202203-2】出行计划（Java）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
