刷题笔记合集🔗

ABR 车路协同场景

问题描述

数轴上有两个点的序列 和 ， 和 均为正整数，、 已经从小到大排好序，、 均肯定不为空。

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

条件：

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

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

原型：

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

输入格式

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

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

输出格式

数对序列，排列顺序满足序列中前面的 后面的 ，前面的 后面的 。

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

样例输入

A={1,3,5},B={2,4,6},R=1

样例输出

(1,2)(3,4)(5,6)

样例	解释说明
样例1	A序列中的1与B序列中的2的距离为1，满足且，因此输出(1,2)；同理，(3,4)和(5,6)都满足条件，所以最终输出(1,2)(3,4)(5,6)。

数据范围

• 和 的大小不超过
• 和 的取值范围为正整数，且不超过
• 为正整数

题解

这道题目乍一看有点复杂，但本质上是在处理两个已排序的序列之间的匹配问题。我们需要找出符合特定条件的A和B元素对。

问题可以这样理解：对于序列A中的每个元素A[i]，我们需要在序列B中找出所有满足两个条件的B[j]：

1. B[j] >= A[i]（B元素不小于A元素）
2. B[j] - A[i] <= R（两元素之间的距离不超过R）

如果A[i]找不到满足条件的B[j]，我们就找出大于等于A[i]的最小的B[j]作为匹配。如果连这样的B[j]都没有，则丢弃A[i]。

这个问题可以通过双指针方法高效解决：

1. 我们为A和B各设置一个指针，初始都指向首元素
2. 对于当前A[i]，我们从当前B指针位置开始查找符合条件的B[j]
3. 如果B[j] < A[i]，则B指针向前移动
4. 如果B[j] >= A[i]，则判断B[j] - A[i] <= R是否成立
5. 如果成立，则记录这对(A[i],B[j])，并继续检查后面的B元素
6. 如果不成立且已经找到至少一个符合条件的B[j]，则停止当前A[i]的查找
7. 如果未找到任何符合条件的B[j]但找到了大于等于A[i]的最小B[j]，则记录这对(A[i],B[j])

由于A和B已经排序，且我们每次只向前移动指针，时间复杂度为O(n+m)，其中n和m分别是序列A和B的长度。这是高效的线性时间算法，非常适合处理题目中指定的数据规模（不超过50）。

参考代码

• Python

import sys
import re
input = lambda: sys.stdin.readline().strip()

# 读取输入
line = input()
# 使用正则表达式解析输入
pattern = r"A=\{(.+)\},B=\{(.+)\},R=(\d+)"
match = re.search(pattern, line)

if match:
    # 提取A序列、B序列和R值
    A = list(map(int, match.group(1).split(',')))
    B = list(map(int, match.group(2).split(',')))
    R = int(match.group(3))
    
    result = []
    
    # 处理每个A中的元素
    for a in A:
        matches = []
        # 找出所有满足条件的B元素
        for b in B:
            # 跳过小于a的B元素
            if b < a:
                continue
                
            # 如果没找到任何匹配或者距离在R范围内
            if len(matches) == 0 or b - a <= R:
                matches.append((a, b))
            else:
                # 已经找到匹配且当前B元素距离超过R
                break
        
        # 将找到的匹配添加到结果中
        result.extend(matches)
    
    # 格式化输出
    output = ''.join([f"({a},{b})" for a, b in result])
    print(output)

• Cpp

#include <iostream>
#include <vector>
#include <regex>
#include <string>
using namespace std;

vector<int> parseNumbers(const string& str) {
    vector<int> nums;
    size_t start = 0;
    size_t end = str.find(',');
    
    while (