【CSP：202203-2】出行计划（Java）

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

题目链接

202203-2 出行计划

题目描述

在这里插入图片描述

求解思路

差分：测试数据中的 $n$ ， $m$ 取值都比较大，直接暴力模拟的话会超时。因此我们在初始化出一个数组，根据做核酸的时间来对应可以出行的行程数量。
res[i]表示在i时刻做核酸可以出行的行程数。
对于在 $q$ 时刻做的核酸，根据题意应该满足 $\leq t_i$ 并且 $t_i-(q+k) < c_i$ 。那么对于第 $i$ 个行程，做核酸的有效时间为 $\in (t_i-k-c_i, t_i-k]$ ，即 $\in [t_i-k-c_i+1, t_i-k]$ 。
那么我们每读取一个行程，就对其进行处理。找到其左右边界进行差分。让在 $[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]);}}
}