华为OD机试之 ABR 车路协同场景（Java源码）

ABR 车路协同场景

题目描述

数轴×有两个点的序列 A={A1， A2, …, Am}和 B={B1, B2, ..., Bn}， Ai 和 Bj 均为正整数， A、 B 已经从小到大排好序， A、 B 均肯定不为空，

给定一个距离 R（正整数），列出同时满足如下条件的所有（Ai， Bj）数对

条件：

1. Ai <= Bj
2. Ai,Bj 距离小于等于 R，但如果 Ai 找不到 R 范围内的 Bj，则列出距它最近的 1 个 Bj，当然此种情况仍然要满足 1，

但如果仍然找不到，就丢弃 Ai。

原型：

车路协同场景，一条路上发生了有很多事件（ A），要通过很多路测设备（ B）广播给路上的车，需要给每个事件找到一个合适的路测设备去发送广播消息。

输入描述

按照人易读的格式输入一行数据，参见输入样例，其中“ ABR={， }”中的每个字符都是关键分割符，输入中无空格，其他均为任意正整数，

输入 A 和 B 已经排好序， A 和 B 的大小不超过 50，正整数范围不会超过 65535。

输出描述

（ Ai,Bj）数对序列，排列顺序满足序列中前面的 Ax<=后面的 Ay，前面的 Bx<=后面的 By，

因为输入 A 和 B 已经排好序，所以实际上输出结果不用特意排序，排序不是考察点。

用例

解析
把题目读懂就完事了，主要是对于没有b-a=r时，要取一个比之前取过的更大一点的b…逻辑不是很绕,具体看代码

示例代码

public class Y2 {
	public static void main(String[] args) {
		int[] arrA = { 1, 3, 5 };
		int[] arrB = { 2, 4, 7 };
		int r = 1;
		for (int a : arrA) {
			int tempB = -1;// 上次取了哪个b
			int near = -1;// 距离a近的
			boolean flag = false;// 是否找到一个b和a匹配
			for (int b : arrB) {
				if (b - a == r && b > tempB) {
					System.out.print("(" + a + "," + b + ")");
					tempB = b;
					flag = true;
					break;
				}
				if (b - a > r) {
					near = b;
					break;
				}
			}
			if (flag == false && near != -1) {
				// 没找到 那么就找一个离a 较近的 若找不到就放弃
				System.out.print("(" + a + "," + near + ")");
			}
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

代码运行截图