自动搬运

查看原文

来自洛谷，原作者为

	mycbxzd 这个家伙很勤快，但还是什么也没有留下

搬运于2025-08-24 22:25:44，当前版本为作者最后更新于2024-04-06 21:58:30，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目翻译

背景

在潘多拉星球，赛车比以往任何时候都更受欢迎。但这些比赛相当不寻常。有 $n$ 辆汽车参加在直线赛道上的比赛。每辆汽车以每秒 $1$ 米的速度移动。赛道上的坐标以米为单位。

第 $i$ 辆汽车在坐标为 $a_{i}$ 和 $b_{i}$ 的两点之间移动，从第二秒开始从点 $a_{i}$ 出发。汽车从 $a_{i}$ 移动到 $b_{i}$，然后从 $b_{i}$ 移动到 $a_{i}$，再从 $a_{i}$ 移动到 $b_{i}$，依此类推。

英俊的迈克想要用炸药淘汰一些汽车。因此，他有 $m$ 个问题。第 $j$ 个问题是：从开始后 $t_{j}$ 秒后，坐标在 $x_{j}$ 和 $y_{j}$ 之间的汽车数量是多少（包括边界）？

你的任务是回答迈克的问题。

输入格式

输入文件的第一行包含两个整数 $n$ 和 $m (1 \le n , m \le 1000)$ -- 比赛中汽车的数量和问题的数量。

接下来的 $n$ 行中，每行包含一辆汽车的描述：两个整数 $a_{i}$ 和 $b_{i} (0 \le a_{i}, b_{i} \le 10^{9}, a_{i} ≠ b_{i})$ -- 汽车 $i$ 移动的两个点的坐标。

接下来的 $m$ 行中，每行包含一个问题的描述：三个整数 $x_{j} , y_{j}$ , 和 $t_{j} (0 \le x_{j} \le y_{j} \le 10^{9}, 0 \le t_{j} \le 10^{9})$ -- 问题 $j$ 的坐标范围和时间。

输出格式

写入输出文件 $m$ 行。每行必须包含一个整数 -- 对应输入文件中给定的问题的答案。

解题

思路:

其实整个题目的核心就是三行代码解决

if ((t / (b[j] - a[j])) % 2 == 1) {l = b[j] - t % (b[j] - a[j]);
else l = a[j] + t % (b[j] - a[j]);
if (l >= x && l <= y)ans++;

• 计算在给定时间 t 后，位于坐标范围 [x, y] 内的车辆数量，并将结果存储在 ans 中。
• 首先，声明了一个名为 l 的 long long 类型变量，用于存储每辆车在给定时间 t 后的位置。
• 然后，通过 if-else 条件语句，根据每辆车在奇数或偶数往返周期内的不同，计算每辆车在给定时间 t 后的位置 l。如果车辆在奇数往返周期内，则 l 被赋值为 b[j] - t % (b[j] - a[j])，否则 l 被赋值为 a[j] + t % (b[j] - a[j])。
• 接着，通过条件判断 if (l >= x && l <= y)，检查每辆车在给定时间 t 后的位置 l 是否在指定的坐标范围 [x, y] 内。若在范围内，则将 ans 加一，表示有一辆车在该时间范围内位于指定的坐标范围内。

式子解释(不知道叫啥了就叫式子吧):

b[j] - t % (b[j] - a[j])

它计算了在给定时间 t 后，位于奇数往返周期内的车辆的位置。具体来说，b[j] - a[j] 表示车辆从起始坐标 a[j] 到结束坐标 b[j] 的距离，而 t % (b[j] - a[j]) 则表示当前往返周期内已经行驶的时间。因为车辆是以每秒 1 米的速度行驶的，所以 (b[j] - t % (b[j] - a[j])) 表示从结束坐标 b[j] 开始倒退，倒退的距离为当前往返周期内已行驶的时间，从而得到了车辆在奇数往返周期内的位置。

a[j] + t % (b[j] - a[j])

它计算了在给定时间 t 后，位于偶数往返周期内的车辆的位置。同样，a[j] 表示车辆的起始坐标，而 t % (b[j] - a[j]) 则表示当前往返周期内已经行驶的时间。因为车辆是以每秒 1 米的速度行驶的，所以 (a[j] + t % (b[j] - a[j])) 表示从起始坐标 a[j] 开始继续向前行驶，行驶的距离为当前往返周期内已行驶的时间，从而得到了车辆在偶数往返周期内的位置。

判断原因解释:

if (l >= x && l <= y)

它用于判断每辆车在给定时间 t 后的位置 l 是否在指定的坐标范围 [x, y] 内。如果车辆的位置 l 大于等于 x 并且小于等于 y，则说明该车辆在指定的坐标范围内，条件成立。

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n, m, a[100010], b[1000010], x, y, t,ans,l;
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)cin >> a[i] >> b[i];
    // 对于每个问题，计算解决方案
    for (int i = 1; i <= m; i++) {
        cin >> x >> y >> t;
        ans = 0; 
        for (int j = 1; j <= n; j++) {
            if ((t / (b[j] - a[j])) % 2 == 1) {
    			// 如果车辆在奇数往返周期内
    			l = b[j] - t % (b[j] - a[j]);
			} else {
    			// 如果车辆在偶数往返周期内
    			l = a[j] + t % (b[j] - a[j]);
			}
            if (l >= x && l <= y)ans++;
        }
        cout << ans << endl;
    }
}