A17036. 长征路上的学习之旅
填空题
中等
知识点
题目描述
长征路上的学习之旅
题目描述
在一条东西向的长征路上，分布着 A 座革命纪念馆和 B 座烈士陵园。以道路最西端为坐标原点，第 i 座革命纪念馆位于坐标 s_i 处，第 j 座烈士陵园位于坐标 t_j 处。为了传承红色基因，红军后代小分队计划开展红色教育活动。每个小分队都在指定位置驻扎，并有一定的探索半径限制。
你需要回答以下 Q 个询问：
第 k 次询问：红军小分队在坐标 x_k 处驻扎，探索半径为 R_k，问在探索范围内，即坐标在 [x_k - R_k, x_k + R_k] 区间内，有多少座建筑（纪念馆和陵园）？（ ）
输入格式
第 1 行：三个正整数 A B Q，分别表示纪念馆数量、陵园数量、询问次数。
第 2 行：A 个正整数 s_1, s_2, ..., s_A，表示各纪念馆坐标。
第 3 行：B 个正整数 t_1, t_2, ..., t_B，表示各陵园坐标。
接下来 Q 行：每行 2 个正整数 x_k R_k，表示驻扎位置和探索半径。
输出格式
输出 Q 行，第 k 行输出第 k 次询问的答案。
数据范围提示
坐标和半径可能达到 10^10，需要使用 long long。
输入样例1
2 2 3
10 30
20 40
20 10
15 5
50 15输出样例1
3
2
1输入样例2
3 4 5
100 300 600
200 400 700 900
250 200
100 50
500 250
700 100
500 500输出样例2
4
1
4
2
7输入样例3
3 2 6
100 500 1000
300 700
100 0
200 50
100 200
500 200
600 500
50 100输出样例3
1
0
2
3
5
1参考答案
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long A, B, Q;
cin >> A >> B >> Q;
// 将纪念馆和陵园的坐标合并到同一个数组
long long n = A + B;
long long a[200005];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
// 排序后即可用二分统计区间内有多少个坐标
sort(a, a + n);
for (int i = 1; i <= Q; i++) {
long long x, R;
cin >> x >> R;
// 本次询问的左右边界
long long l = x - R;
long long r = x + R;
// left 是第一个 >= l 的位置编号
long long left = lower_bound(a, a + n, l) - a;
// right 是第一个 > r 的位置编号
long long right = upper_bound(a, a + n, r) - a;
cout << right - left << endl;
}
return 0;
}答案解析
本题只关心建筑坐标，不关心建筑类别。可以把纪念馆和陵园坐标合并到同一个数组中：
1. 合并所有坐标；
2. 对坐标数组排序；
3. 每次询问区间 [L, R] = [x - r, x + r]；
4. 用 lower_bound 找到第一个 >= L 的位置；
5. 用 upper_bound 找到第一个 > R 的位置；
6. 两个迭代器相减就是区间内建筑数量。
上一题
下一题