刷题笔记合集🔗

AI面板识别

问题描述

小兰负责一个AI识别项目，该系统需要识别面板上的 个指示灯，灯的大小一样，任意两个之间无重叠。

由于AI识别存在误差，每次识别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置（左上角 ，右下角 ）。

现在需要输出先行后列排序的指示灯的编号，排序规则：

1. 每次在尚未排序的灯中挑选最高的灯作为基准灯；
2. 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 灯高度的一半）。

输入格式

第一行为 ，表示灯的个数。

接下来 行，每行为1个灯的坐标信息，格式为：

编号

输出格式

排序后的编号列表，编号之间以空格分隔。

样例输入

5
1 0 0 2 2
2 6 1 8 3
3 3 2 5 4
5 5 4 7 6
4 0 4 2 6

样例输出

1 2 3 4 5

数据范围

题解

这道题主要考察排序和分组的逻辑处理。题目要求我们按照"先行后列"的方式对灯进行排序，核心在于如何确定哪些灯属于同一行。

首先，我们需要理解题目中"同一行"的定义：两个灯的高度差不超过灯的半径，就认为它们在同一行。每个灯的高度是由坐标 和 确定的，灯的中心坐标可以计算为 ，灯的半径为 。

解题步骤：

1. 将所有灯按照y坐标（高度）从小到大排序
2. 从最高的灯（y坐标最小）开始，将它作为基准灯
3. 找出与基准灯在同一行的所有灯（y坐标差不超过灯半径）
4. 对同一行的灯按照x坐标从小到大排序
5. 将这一行灯的编号加入结果集
6. 继续处理下一行，直到所有灯都处理完毕

这种方法的时间复杂度为 ，主要由排序操作决定。对于给定的数据范围（），这个复杂度是完全可以接受的。

一个关键点是需要注意处理最后一行的灯，确保它们也被正确地加入到结果中。

参考代码

• Python

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

class Light:
    def __init__(self, id, x, y, r):
        self.id = id  # 编号
        self.x = x    # 圆心x坐标
        self.y = y    # 圆心y坐标
        self.r = r    # 半径

# 读取输入
n = int(input())
lights = []
for _ in range(n):
    data = list(map(int, input().split()))
    id, x1, y1, x2, y2 = data
    # 计算圆心坐标和半径
    x = (x1 + x2) // 2
    y = (y1 + y2) // 2
    r = (x2 - x1) // 2
    lights.append(Light(id, x, y, r))

# 按y坐标排序
lights.sort(key=lambda l: l.y)

# 结果集
res = []

# 处理每一行
row_lights = []
base = lights[0]
row_lights.append(base)

for i in range(1, len(lights)):
    cur = lights[i]
    
    # 判断是否与基准灯在同一行
    if cur.y - base.y <= base.r:
        row_lights.append(cur)
    else:
        # 不在同一行，处理当前行
        row_lights.sort(key=lambda l: l.x)
        res.extend([l.id for l in row_lights])
        
        # 开始新的一行
        row_lights = [cur]
        base = cur

# 处理最后一行
if row_lights:
    row_lights.sort(key=lambda l: l.x)
    res.extend([l.id for l in row_lights])

# 输出结果
print(" ".join(map(str, res)))

• Cpp

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

// 灯的结构体
struct Light {
    int id;  // 编号
    int x;   // 中心x坐标
    int y;   // 中心y坐标
    int r;   // 半径
    
    Light(int id, int x, int y, int r) : id(id), x(x), y(y), r(r) {}
};

int main() {
    int n;
    cin >> n;
    
    vector<Light> lights;
    for (int i = 0; i < n; i++) {
        int id, x1, y1, x2, y2;
        cin >> id >> x1 >> y1 >> x2 >> y2;
        
        // 计算中心点和半径
        int x = (x1 + x2) / 2;
        int y = (y1 + y2) / 2;
        int r = (x2 - x1) / 2;
        
        lights.emplace_back(id, x, y, r);