E卷-刷题笔记合集🔗

问题描述

小兰负责一个车路协同系统。在一条路上发生了很多事件（序列 ），需要通过路测设备（序列 ）广播给路上的车。每个事件都需要找到一个合适的路测设备来发送广播消息。

给定两个已排序的正整数序列 和 ，以及一个距离值 ，请帮助小兰找出所有满足条件的 数对。

配对需要满足以下条件：

1. 
2. 如果存在多个 满足 ，则全部列出
3. 如果不存在满足 的 ，则选择大于 的最小的
4. 如果找不到大于 的 ，则放弃这个

输入格式

输入为一行，格式为 A={a1,a2,...,am},B={b1,b2,...,bn},R=r，其中：

• 和 为正整数，且已按升序排列
• 为正整数
• 输入中不含空格

输出格式

输出所有满足条件的数对 ，按照 升序排列。

样例输入1

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

样例输出1

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

样例输入2

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

样例输出2

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

样例解释

数据范围

• 
• 
• 
• 序列 和 已按升序排列

题解

这是一个配对问题，主要考察如何根据给定条件为每个事件找到合适的路测设备。

解题思路：

1. 首先需要解析输入字符串，提取出A序列、B序列和R值。可以使用正则表达式或字符串分割。

2. 对于A中的每个元素a：

   • 遍历B序列，找出所有满足条件的b
   • 如果存在b-a≤R的情况，输出所有这样的配对
   • 如果不存在，则输出第一个大于a的b（如果存在）

3. 关键点：

   • 由于序列已经排序，一旦发现b-a>R，后面的b就不需要再检查了
   • 需要记录是否找到过满足条件的配对，以决定是否需要输出最近的配对

时间复杂度：，其中 和 分别是序列 和 的长度。

参考代码

import re

def solve():
    # 读取输入
    s = input()
    pattern = r"A=\{(.+)\},B=\{(.+)\},R=(.+)"
    match = re.search(pattern, s)
    
    # 解析输入数据
    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:
        found = False
        # 遍历B序列寻找匹配
        for b in B:
            # 跳过小于a的b
            if b < a:
                continue
            # 如果距离在R范围内或者是第一个大于a的b
            if b - a <= R or not found:
                result.append(f"({a},{b})")
                found = True
            else:
                break
    
    # 输出结果
    print("".join(result))

if __name__ == "__main__":
    solve()

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

vector<int> parse_nums(string s) {
    vector<int> nums;
    size_t pos = 0;