【华为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解法

• 解题思路：
• 这段代码的目的是处理一组灯光的位置和大小，并按照特定的规则对这些灯光进行排序。根据给定的灯光的坐标和半径，程序将这些灯光按垂直方向（y坐标）分组，然后在每个组内按水平方向（x坐标）排序，最后输出这些灯光的索引。

具体步骤如下：

输入解析：

首先，读取灯光的数量 n。
然后，读取每个灯光的坐标和半径信息，使用这些信息创建 Light 类的实例，存储在一个列表 lights 中。
灯光位置与排序规则：

每个灯光的坐标 (x, y) 是由其给定的两个角的坐标计算得来的：x = (x1 + x2) // 2 和 y = (y1 + y2) // 2。
灯光的半径 radius 是由给定的两个角的横向距离计算得来的：radius = (x2 - x1) // 2。
按垂直方向分组：

将所有灯光按照 y 坐标进行排序，确保灯光从上到下排列。
在排序后的灯光列表中，尝试将尽可能多的灯光分配到同一组中。分组的标准是：当前灯光的 y 坐标与上一灯光的 y 坐标之差小于等于该灯光的半径。
组内按水平方向排序：

在每一组内，将灯光按 x 坐标从左到右排序。
输出结果：

输出每一组中灯光的索引，按排序后的顺序输出所有组的灯光索引

# 定义 Light 类来存储灯光的信息
class Light:
    def __init__(self, idx, x1, y1, x2, y2):
        self.idx = idx  # 灯光的索引
        self.x = (x1 + x2) // 2  # 计算灯光的横坐标：两个角的中点
        self.y = (y1 + y2) // 2  # 计算灯光的纵坐标：两个角的中点
        self.radius = (x2 - x1) // 2  # 计算灯光的半径：两个角的横向距离的一半

# 读取输入，获取灯光的数量 n
n = int(input())

# 读取每个灯光的信息，创建 Light 对象并存入列表 lights
lights = [Light(*map(int, input().split())) for _ in range(n)]

# 按照灯光的 y 坐标进行排序
lights.sort(key=lambda l: l.y)

# 初始化结果列表和临时行列表
result = []
temp_row = []

# 初始的基准灯光是排序后的第一个灯光
base_light = lights[0]
temp_row.append(base_light)

# 遍历灯光列表，从第二个灯光开始
for i in range(1, len(lights)):
    light = lights[i]
    # 如果当前灯光与基准灯光的纵坐标差小于等于基准灯光的半径，属于同一行
    if light.y - base_light.y <= base_light.radius:
        temp_row.append(light)
    else:
        # 如果当前灯光不在同一行，先按 x 坐标排序并加入结果
        temp_row.sort(key=lambda l: l.x)
        result.extend([l.idx for l in temp_row])  # 将该行灯光的索引加入结果列表
        temp_row.clear()  # 清空临时行
        base_light = light  # 更新基准灯光为当前灯光
        temp_row.append(base_light)  # 将当前灯光加入新的行

# 如果最后一行还有灯光，处理这一行
if temp_row:
    temp_row.sort(key=lambda l: l.x)  # 按 x 坐标排序
    result.extend([l.idx for l in temp_row])  # 将该行灯光的索引加入结果列表

# 输出结果，灯光的索引以空格分隔
print(" ".join(map(str, result)))

• 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

java解法

• 解题思路
• 这段代码的目标是根据给定的灯光信息（每个灯光的坐标和半径），按照垂直方向分组灯光，并在每个组内按水平方向排序，最终输出每个灯光的索引。

具体步骤如下：

输入解析：

首先读取灯光的数量 n。
对于每个灯光，读取其编号 id、两个角点的坐标 (x1, y1) 和 (x2, y2)，然后根据这些信息计算出灯光的中心坐标 (x, y) 和半径 r。
灯光排序：

通过 y 坐标对所有灯光进行排序，这样可以按垂直方向将灯光分为不同的组。
分组灯光：

遍历排序后的灯光列表，将 y 坐标差值小于等于当前灯光半径的灯光归为同一组。每一组的灯光都需要按照 x 坐标进行排序。
输出排序后的灯光编号：

对每一组灯光，根据 x 坐标排序并输出其编号。每组灯光的编号按从左到右的顺序输出。
最终输出：

输出所有组的灯光编号，确保它们的顺序是正确的

import java.util.*;

public class Main {
    
    public static void main(String[] args) {
        // 创建 Scanner 对象来读取输入
        Scanner scanner = new Scanner(System.in);
        
        // 读取灯光的数量
        int n = scanner.nextInt();
        
        // 创建一个灯光数组来存储所有的灯光
        Light[] lights = new Light[n];

        // 循环读取每个灯光的信息
        for (int i = 0; i < n; i++) {
            int id = scanner.nextInt();  // 灯光编号
            int x1 = scanner.nextInt();  // 第一个角的 x 坐标
            int y1 = scanner.nextInt();  // 第一个角的 y 坐标
            int x2 = scanner.nextInt();  // 第二个角的 x 坐标
            int y2 = scanner.nextInt();  // 第二个角的 y 坐标
            
            // 计算灯光的中心坐标 (x, y) 和半径 r
            lights[i] = new Light(id, (x1 + x2) / 2, (y1 + y2) / 2, (x2 - x1) / 2);
        }

        // 调用 determineOrder 方法得到最终的排序结果并输出
        System.out.println(determineOrder(lights));
    }

    // 该方法用于确定灯光的排序结果
    public static String determineOrder(Light[] lights) {
        // 按照 y 坐标对灯光进行排序
        Arrays.sort(lights, Comparator.comparingInt(light -> light.y));

        // 使用 StringBuilder 来高效构建结果字符串
        StringBuilder result = new StringBuilder();
        
        // 创建一个 List 用于存储当前行的灯光
        List<Light> sameRow = new ArrayList<>();
        
        // 将第一个灯光设为基准灯光
        Light reference = lights[0];
        sameRow.add(reference);

        // 遍历剩下的灯光
        for (int i = 1; i < lights.length; i++) {
            Light current = lights[i];
            
            // 如果当前灯光的 y 坐标与基准灯光的 y 坐标差值小于等于基准灯光的半径，
            // 说明它们可以在同一行，加入同一行的灯光列表
            if (current.y - reference.y <= reference.r) {
                sameRow.add(current);
            } else {
                // 如果当前灯光不在同一行，先对当前行的灯光按 x 坐标排序
                sameRow.sort(Comparator.comparingInt(light -> light.x));
                
                // 将当前行的所有灯光编号加入结果字符串
                for (Light light : sameRow) {
                    result.append(light.id).append(" ");
                }
                
                // 清空当前行的灯光列表
                sameRow.clear();
                
                // 更新基准灯光为当前灯光，并开始新的行
                reference = current;
                sameRow.add(reference);
            }
        }

        // 如果最后一行灯光还没有被处理，进行处理
        if (!sameRow.isEmpty()) {
            sameRow.sort(Comparator.comparingInt(light -> light.x));  // 按 x 坐标排序
            for (Light light : sameRow) {
                result.append(light.id).append(" ");
            }
        }

        // 返回最终结果字符串，去掉尾部的多余空格
        return result.toString().trim();
    }
}

// 定义 Light 类来存储每个灯光的信息
class Light {
    int id;  // 灯光编号
    int x;   // 灯光的 x 坐标（中心）
    int y;   // 灯光的 y 坐标（中心）
    int r;   // 灯光的半径

    // 构造函数，初始化灯光的编号、坐标和半径
    public Light(int id, int x, int y, int r) {
        this.id = id;
        this.x = x;
        this.y = y;
        this.r = r;
    }
}

• 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
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100

C++解法

• 解题思路

更新中

• 1

C解法

• 解题思路

• 该程序的目的是根据给定灯光的坐标和半径信息，按照特定规则输出灯光的编号：

输入解析：

每个灯光的编号 id 和它的两个角点坐标 (x1, y1) 和 (x2, y2)，程序需要通过这些数据计算出灯光的中心坐标 (x, y) 和半径 r。
排序规则：

首先根据 y 坐标对所有灯光进行排序。
然后根据灯光的 y 坐标差值判断是否处于同一行，如果是，则按 x 坐标排序；如果不是，则将当前行的灯光按 x 坐标输出。
分组灯光：

程序将灯光分为几组：如果灯光 y 坐标差值小于等于当前灯光的半径，则认为它们在同一行。
对每行内的灯光进行 x 坐标排序，然后输出它们的编号

#include 
#include 

// 定义灯光的结构体，包含灯光编号、x、y 坐标及半径
typedef struct {
    int id;  // 灯光编号
    int x;   // 灯光中心的 x 坐标
    int y;   // 灯光中心的 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) {
        // 按 x 坐标排序
        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];

    // 读取每个灯光的信息
    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(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
• 90
• 91
• 92
• 93
• 94
• 95
• 96
• 97
• 98
• 99
• 100
• 101

JS解法

• 解题思路

• 本题的目标是处理一组灯光的信息，并根据灯光的 y 坐标来排序它们，确定它们的顺序，按照以下规则：

灯光根据 y 坐标排序，若 y 坐标差距小于等于某个基准灯光的半径 r，则认为这些灯光在同一行。
同一行内的灯光按照 x 坐标进行排序，然后输出它们的编号。
如果灯光属于不同的行，则按 y 坐标分组并按 x 坐标排序。

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); // 将每行输入存储到 data 数组中

    if (data.length === 1) {
        numberOfLights = parseInt(data[0]); // 第一行是灯光数量，转换为数字
    }

    // 当读取到足够的输入数据后，开始处理
    if (numberOfLights && data.length === numberOfLights + 1) {
        data.shift(); // 删除第一行（灯光数量）

        // 处理灯光数据
        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 (y 坐标) 排序
    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];

        // 如果当前灯光和基准灯光的 y 坐标差值小于等于基准灯光的半径，则认为它们在同一行
        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);
    }

    return finalOrder.join(" "); // 返回最终的灯光编号顺序
}

// 输出当前行的灯光编号，并按 x 坐标排序
function finalizeRow(row, result) {
    row.sort((a, b) => a.midX - b.midX) // 按 x 坐标升序排序
        .forEach((light) => result.push(light.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

注意：

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