【华为OD-E卷-ai面板识别 100分（python、java、c++、js、c）】

题目

AI识别到面板上有N（1 ≤ N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠。
由于AI识别误差，每次别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)，
请输出先行后列排序的指示灯的编号，
排序规则：
每次在尚未排序的灯中挑选最高的灯作为的基准灯， 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）。
输入描述 第一行为N，表示灯的个数 接下来N行，每行为1个灯的坐标信息，
格式为：
编号 x1 y1 x2 y2
编号全局唯一 1 ≤ 编号 ≤ 100 0 ≤ x1 < x2 ≤ 1000 0 ≤ y1 < y2 ≤ 1000 输出描述 排序后的编号列表，编号之间以空格分隔

用例

用例一：

输入：

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
• 6

输出：

1 2 3 4 5

• 1

python解法

• 解题思路：
• 这道题目涉及的是按行排列一组灯光，每个灯光的位置和半径给定，目标是将这些灯光按照一定规则排序后输出其编号。

输入与数据结构：

输入的每一行包含五个数：灯光的编号（id）、灯光的左上角坐标（cx、cy）、右下角坐标（r）和宽度。通过这些数据可以确定每个灯光的圆心坐标、半径以及该灯光的 id。
目标：

我们需要先按灯光的 cy（圆心的纵坐标）进行排序，这样可以将所有在同一行的灯光分组。
对于每一行的灯光，需要根据 cx（圆心的横坐标）进行排序。最终输出的结果是按行排序后，每行灯光按 cx 排序后的 id 组成的序列。
步骤：

首先，先将输入的灯光数据转换成 Light 对象，每个对象包含其编号、圆心坐标和半径。
然后，按照纵坐标 cy 对灯光进行排序，将相同纵坐标（同一行）的灯光分到一起。
对于每行的灯光，按横坐标 cx 排序，并输出其 id。

class Light:
    # 灯光类，初始化时需要提供灯光的id、圆心坐标 (cx, cy) 和半径 r
    def __init__(self, id, cx, cy, r):
        self.id = id  # 灯光的编号
        self.cx = cx  # 圆心横坐标
        self.cy = cy  # 圆心纵坐标
        self.r = r    # 半径

# 输入n代表灯光数量
n = int(input())
# 输入灯光数据：每个灯光包含 [id, left, top, right, bottom] 信息
arr = [list(map(int, input().split())) for _ in range(n)]

# 将输入的灯光数据转换成 Light 对象，计算圆心和半径
lights = [Light(ele[0], (ele[1] + ele[3]) // 2, (ele[2] + ele[4]) // 2, (ele[3] - ele[1]) // 2) for ele in arr]

def sort_lights():
    # 按照纵坐标 (cy) 排序，这样可以将同一行的灯光放在一起
    lights.sort(key=lambda l: l.cy)
    
    res = []  # 存储最终排序后的灯光id
    same_row = []  # 临时存储同一行的灯光
    base = lights[0]  # 设置基准灯光为第一个灯光
    same_row.append(base)  # 将基准灯光加入到同一行灯光中

    # 遍历灯光列表，从第二个灯光开始
    for i in range(1, len(lights)):
        cur = lights[i]  # 当前灯光
        # 如果当前灯光的纵坐标 (cy) 和基准灯光的纵坐标之差小于等于基准灯光的半径，则认为它们在同一行
        if cur.cy - base.cy <= base.r:
            same_row.append(cur)  # 当前灯光加入到同一行
        else:
            # 如果当前灯光不在同一行，首先按横坐标 (cx) 对这一行的灯光进行排序
            same_row.sort(key=lambda l: l.cx)
            # 将这一行的灯光id加入结果
            res.extend([l.id for l in same_row])
            same_row.clear()  # 清空当前行的灯光
            base = cur  # 更新基准灯光
            same_row.append(base)  # 将当前灯光加入新的行

    # 如果最后还有一行灯光没有加入结果，按横坐标 (cx) 排序后加入
    if same_row:
        same_row.sort(key=lambda l: l.cx)
        res.extend([l.id for l in same_row])

    # 返回结果，灯光的id按照每行的顺序排列
    return " ".join(map(str, res))

# 输出排序后的灯光编号
print(sort_lights())

• 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
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51

java解法

• 解题思路
• 这道题目要求我们根据灯光的坐标和半径对灯光进行排序，并输出灯光的编号。具体步骤如下：

输入数据：

输入首先包含一个整数 n，表示灯光的数量。
接下来，输入 n 行，每行包含五个整数：灯光的 id、左上角坐标 (x1, y1)、右下角坐标 (x2, y2)。
目标：

每个灯光的实际位置是其圆心，圆心坐标可以通过 (x1 + x2) / 2 和 (y1 + y2) / 2 计算得到，半径可以通过 (x2 - x1) / 2 计算得到。
将灯光按照纵坐标 y 排序，确保在同一行的灯光按横坐标 x 排序后输出。
处理同一行的灯光，将相同纵坐标的灯光分到一组，然后按横坐标排序后输出每一行灯光的 id。
步骤：

先创建一个 Indicator 类来存储每个灯光的信息，包括 id、圆心的坐标 (x, y) 和半径 radius。
然后将灯光按纵坐标 y 排序，接着根据 radius 来判断哪些灯光属于同一行。
对于每一行的灯光，根据横坐标 x 进行排序，最后按顺序输出灯光的 id。

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        
        // 输入灯光数量n
        int n = input.nextInt();
        // 创建灯光数组
        Indicator[] indicators = new Indicator[n];

        // 输入每个灯光的数据：id, x1, y1, x2, y2
        for (int i = 0; i < n; i++) {
            int id = input.nextInt();
            int x1 = input.nextInt();
            int y1 = input.nextInt();
            int x2 = input.nextInt();
            int y2 = input.nextInt();
            
            // 创建Indicator对象，并计算灯光的圆心坐标 (x, y) 和半径 radius
            indicators[i] = new Indicator(id, (x1 + x2) / 2, (y1 + y2) / 2, (x2 - x1) / 2);
        }

        // 调用sortIndicators方法返回排序后的灯光编号，并输出
        System.out.println(sortIndicators(indicators));
    }

    // 排序灯光的核心方法
    public static String sortIndicators(Indicator[] indicators) {
        // 按照灯光的纵坐标 y 排序
        Arrays.sort(indicators, Comparator.comparingInt(ind -> ind.y));
        
        // 用于存储同一行的灯光
        List<Indicator> rowGroup = new ArrayList<>();
        StringBuilder sortedIds = new StringBuilder();
        
        // 设置当前行的基准灯光
        Indicator current = indicators[0];
        rowGroup.add(current);  // 将基准灯光加入行组

        // 遍历灯光数组，处理每个灯光
        for (int i = 1; i < indicators.length; i++) {
            Indicator next = indicators[i];
            // 如果当前灯光与基准灯光的纵坐标差不超过半径，说明它们在同一行
            if (next.y - current.y <= current.radius) {
                rowGroup.add(next);  // 加入同一行
            } else {
                // 当前行的灯光已处理完，按横坐标 x 排序
                rowGroup.sort(Comparator.comparingInt(ind -> ind.x));
                // 将这一行的灯光编号添加到结果中
                for (Indicator ind : rowGroup) {
                    sortedIds.append(ind.id).append(" ");
                }
                rowGroup.clear();  // 清空当前行的灯光
                current = next;  // 更新基准灯光为当前灯光
                rowGroup.add(current);  // 将当前灯光加入新的一行
            }
        }

        // 如果最后还有灯光未处理，按横坐标 x 排序后加入
        if (!rowGroup.isEmpty()) {
            rowGroup.sort(Comparator.comparingInt(ind -> ind.x));
            for (Indicator ind : rowGroup) {
                sortedIds.append(ind.id).append(" ");
            }
        }

        // 返回结果，并去除末尾多余的空格
        return sortedIds.toString().trim();
    }
}

// Indicator 类表示每个灯光的属性
class Indicator {
    int id;     // 灯光的编号
    int x;      // 圆心的横坐标
    int y;      // 圆心的纵坐标
    int radius; // 半径

    // 构造函数，初始化灯光的id、x、y和半径
    public Indicator(int id, int x, int y, int radius) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.radius = radius;
    }
}

• 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
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89

C++解法

• 解题思路

更新中

• 1

C解法

• 解题思路

• 题目要求我们根据给定的一组灯光信息（每个灯光的编号、左上角和右下角坐标），将灯光按照一定规则进行排序并输出。具体步骤如下：

输入数据结构：

输入一个整数 n 表示灯光的数量。
对于每个灯光，输入五个整数：灯光的编号 id，左上角坐标 (x1, y1) 和右下角坐标 (x2, y2)。
目标：

每个灯光的实际位置是其圆心，圆心坐标可以通过 (x1 + x2) / 2 和 (y1 + y2) / 2 计算得到，半径可以通过 (x2 - x1) / 2 计算得到。
将灯光按纵坐标 y 排序，确保在同一行的灯光按横坐标 x 排序后输出。
处理同一行灯光：

根据纵坐标的差值判断灯光是否属于同一行：如果当前灯光与上一行灯光的纵坐标差不超过基准灯光的半径（y 坐标差小于等于半径），则认为它们在同一行。
对于每一行灯光，按横坐标 x 排序，并按顺序输出灯光的 id。
步骤：

使用结构体 Light 来存储每个灯光的编号、圆心坐标和半径。
通过 qsort 按照纵坐标对灯光进行排序，然后根据基准灯光的 y 坐标差值来分组处理。
对每一组同一行的灯光按横坐标 x 排序，最后输出每行灯光的 id。

#include 
#include 

// 定义灯光结构体，包含id, 圆心坐标 (x, y) 和半径 r
typedef struct {
    int id;
    int x;
    int y;
    int r;
} Light;

// 比较函数，用于按照纵坐标 y 排序灯光
int compareY(const void* a, const void* b) {
    Light* lightA = (Light*)a;
    Light* lightB = (Light*)b;
    return lightA->y - lightB->y; // 纵坐标较小的排前面
}

// 比较函数，用于按照横坐标 x 排序灯光
int compareX(const void* a, const void* b) {
    Light* lightA = (Light*)a;
    Light* lightB = (Light*)b;
    return lightA->x - lightB->x; // 横坐标较小的排前面
}

// 确定灯光的输出顺序
void determineOrder(Light lights[], int n) {
    // 按照纵坐标 y 排序灯光
    qsort(lights, n, sizeof(Light), compareY);
    
    Light sameRow[n];  // 存储当前行的灯光
    int sameRowCount = 0;  // 当前行的灯光数量
    Light reference = lights[0];  // 设置基准灯光
    sameRow[sameRowCount++] = reference;  // 将基准灯光加入当前行

    // 遍历灯光数组，判断同一行的灯光
    for (int i = 1; i < n; i++) {
        Light current = lights[i];
        // 判断当前灯光是否与基准灯光在同一行：y差值小于等于基准灯光的半径
        if (current.y - reference.y <= reference.r) {
            sameRow[sameRowCount++] = current;  // 加入当前行
        }
        else {
            // 如果当前灯光不在同一行，先对当前行的灯光按横坐标 x 排序
            qsort(sameRow, sameRowCount, sizeof(Light), compareX);
            // 输出当前行的所有灯光编号
            for (int j = 0; j < sameRowCount; j++) {
                printf("%d ", sameRow[j].id);
            }
            sameRowCount = 0;  // 清空当前行
            reference = current;  // 更新基准灯光为当前灯光
            sameRow[sameRowCount++] = reference;  // 将当前灯光加入新的行
        }
    }

    // 输出最后一行的灯光编号
    if (sameRowCount > 0) {
        qsort(sameRow, sameRowCount, sizeof(Light), compareX);
        for (int j = 0; j < sameRowCount; j++) {
            printf("%d ", sameRow[j].id);
        }
    }

    // 输出换行符
    printf("\n");
}

// 主函数
int main() {
    int n;
    scanf("%d", &n);  // 输入灯光的数量
    Light lights[n];  // 声明灯光数组

    // 输入每个灯光的信息：id, 左上角坐标 (x1, y1), 右下角坐标 (x2, y2)
    for (int i = 0; i < n; i++) {
        int id, x1, y1, x2, y2;
        scanf("%d %d %d %d %d", &id, &x1, &y1, &x2, &y2);
        lights[i].id = id;
        lights[i].x = (x1 + x2) / 2;  // 计算灯光的圆心横坐标
        lights[i].y = (y1 + y2) / 2;  // 计算灯光的圆心纵坐标
        lights[i].r = (x2 - x1) / 2;  // 计算灯光的半径
    }

    // 调用determineOrder函数对灯光进行排序并输出结果
    determineOrder(lights, n);

    return 0;
}

• 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
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83
• 84
• 85
• 86
• 87
• 88
• 89

JS解法

• 解题思路

• 本题的核心是根据每个灯光的信息（圆形区域的左上角和右下角坐标），计算每个灯光的圆心位置和半径，并按照一定的规则排序这些灯光。具体要求是：

首先按照纵坐标（y）对灯光进行排序，确保同一水平线上的灯光按顺序排列。
同一行的灯光按横坐标（x）排序。
需要判断哪些灯光位于同一行，判断规则是两个灯光的纵坐标差是否在基准灯光的半径范围内（即：nextLight.midY - currentLight.midY <= currentLight.rad）。
处理步骤：
输入解析：通过 readline 持续读取输入，直到读取到所有的灯光数据。
数据转换：解析每个灯光的坐标信息，计算每个灯光的圆心坐标（midX, midY）和半径（rad）。
排序逻辑：
纵坐标排序：按 midY 排序，确保灯光按照从上到下的顺序排列。
同一行的灯光判断：判断灯光是否在同一行，如果在同一行，则将它们按横坐标 midX 排序，输出灯光的 id。
输出结果：每次处理完一行灯光后，输出该行灯光的 id，最后输出所有灯光的排序结果。

// 使用 readline 创建接口以便读取输入
const readline = require("readline");

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout,
});

// 用来存储输入的数据
let data = [];
let numberOfLights;

// 每次读取一行数据
rl.on("line", (line) => {
    data.push(line); // 将每行数据存入数组

    // 第一行是灯光的数量
    if (data.length === 1) {
        numberOfLights = parseInt(data[0]);  // 读取灯光数量
    }

    // 当读取到足够的灯光数据时，开始处理
    if (numberOfLights && data.length === numberOfLights + 1) {
        data.shift(); // 去掉第一个元素，即灯光的数量

        // 将每行灯光数据解析为对象，存储灯光的id和计算出的圆心坐标、半径
        const lights = data.map((str) => {
            const [id, x1, y1, x2, y2] = str.split(" ").map(Number);
            return { 
                id, 
                midX: (x1 + x2) / 2, // 计算圆心的横坐标
                midY: (y1 + y2) / 2, // 计算圆心的纵坐标
                rad: (x2 - x1) / 2 // 计算圆的半径
            };
        });

        // 调用函数来计算并打印结果
        console.log(computeOrder(lights));

        // 清空数据准备下一轮的输入
        data = [];
    }
});

// 计算灯光的排序顺序
function computeOrder(lightArray) {
    // 先按纵坐标 midY 排序
    lightArray.sort((lightA, lightB) => lightA.midY - lightB.midY);

    const finalOrder = []; // 存储最终的排序结果
    let rowLights = []; // 存储当前行的灯光
    let currentLight = lightArray[0]; // 当前行的基准灯光
    rowLights.push(currentLight); // 将基准灯光加入当前行

    // 遍历灯光数组，分行处理灯光
    for (let i = 1; i < lightArray.length; i++) {
        const nextLight = lightArray[i];

        // 如果当前灯光与基准灯光的纵坐标差在半径范围内，认为它们在同一行
        if (nextLight.midY - currentLight.midY <= currentLight.rad) {
            rowLights.push(nextLight); // 加入当前行
        } else {
            // 当前行已结束，处理并输出该行的灯光
            finalizeRow(rowLights, finalOrder);
            rowLights = [nextLight]; // 当前灯光开始新的行
            currentLight = nextLight; // 更新基准灯光为当前灯光
        }
    }

    // 处理最后一行的灯光
    if (rowLights.length > 0) {
        finalizeRow(rowLights, finalOrder);
    }

    // 返回最终排序后的灯光编号（id）
    return finalOrder.join(" ");
}

// 将当前行的灯光按横坐标 midX 排序，并将 id 输出
function finalizeRow(row, result) {
    row.sort((a, b) => a.midX - b.midX).forEach((light) => result.push(light.id)); // 按横坐标排序，并收集 id
}

• 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
• 30
• 31
• 32
• 33
• 34
• 35
• 36
• 37
• 38
• 39
• 40
• 41
• 42
• 43
• 44
• 45
• 46
• 47
• 48
• 49
• 50
• 51
• 52
• 53
• 54
• 55
• 56
• 57
• 58
• 59
• 60
• 61
• 62
• 63
• 64
• 65
• 66
• 67
• 68
• 69
• 70
• 71
• 72
• 73
• 74
• 75
• 76
• 77
• 78
• 79
• 80
• 81
• 82
• 83

注意：

如果发现代码有用例覆盖不到的情况，欢迎反馈！会在第一时间修正，更新。
解题不易，如对您有帮助，欢迎点赞/收藏