E卷-刷题笔记合集🔗

题目描述

AI系统识别到面板上有 个指示灯（），这些灯大小一样，任意两个之间无重叠。

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

请按照以下规则对指示灯进行排序并输出编号：

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

输入格式

第一行输入一个整数 ，表示指示灯的数量。

接下来 行，每行包含5个整数，格式为：

编号 x1 y1 x2 y2

其中：

• 编号全局唯一，满足 编号
• 坐标满足
• 坐标满足

输出格式

输出一行，包含排序后的指示灯编号，编号之间用空格分隔。

样例输入

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. 首先选择最高的灯1作为基准
2. 灯2与灯1在同一行(y坐标差≤半径)
3. 灯3与灯1、2不在同一行,作为新的一行
4. 灯4、5组成最后一行
5. 每行内部按x坐标排序

提示

1. 计算灯的中心点和半径可以简化判断
2. 先按y坐标排序,再处理同一行的情况
3. 注意不要遗漏最后一行的灯

数据范围

• 
• 编号
• 
• 

题解

这是一个排序题,主要考察如何按照特定规则对指示灯进行分组和排序。

解题思路:

1. 预处理:

   • 计算每个灯的圆心坐标(x,y)和半径r
   • 按y坐标升序排序所有灯

2. 分组处理:

   • 取最高的灯作为基准灯
   • 遍历其他灯,如果y坐标差≤基准灯半径,则属于同一行
   • 同一行的灯按x坐标排序
   • 重复此过程直到所有灯都处理完

3. 关键点:

   • 使用圆心坐标简化计算
   • 需要特别处理最后一行
   • 保持编号的输出顺序

时间复杂度: ，主要来自排序操作。

参考代码

class Lamp:
    def __init__(self, idx, x, y, rad):
        self.idx = idx    # 灯的编号
        self.x = x        # 中心x坐标
        self.y = y        # 中心y坐标 
        self.rad = rad    # 灯的半径

def solve():
    # 读取输入
    n = int(input())
    lamps = []
    for _ in range(n):
        idx, x1, y1, x2, y2 = map(int, input().split())
        # 计算中心点和半径
        x = (x1 + x2) // 2
        y = (y1 + y2) // 2
        rad = (x2 - x1) // 2
        lamps.append(Lamp(idx, x, y, rad))
    
    # 按y坐标升序排序
    lamps.sort(key=lambda l: l.y)
    
    res = []
    row = []
    base = lamps[0]
    row.append(base)
    
    # 处理每个灯
    for i in range(1, n):
        curr = lamps[i]
        if curr.y - base.y <= base.rad:
            # 同一行
            row.append(curr)
        else:
            # 新的一行
            row.sort(key=lambda l: l.x)
            res.extend(l.idx for l in row)
            row = [curr]
            base = curr
    
    # 处理最后一行
    if row:
        row.sort(key=lambda l: l.x)
        res.extend(l.idx for l in row)
    
    print(" ".join(map(str, res)))

if __name__ == "__main__":
    solve()

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

struct Lamp {
    int idx;  // 灯的编号
    int x;    // 中心x坐标
    int y;    // 中心y坐标
    int rad;  // 灯的半径
    
    Lamp(int i, int cx, int cy, int r): 
        idx(i), x(cx), y(cy), rad(r) {}
};

int main() {
    int n;
    cin >> n;
    
    vector<Lamp> lamps;
    for(i