AI面板识别 - 华为OD统一考试

OD统一考试 (B卷)

分值： 100分

题解： Java / Python / C++

题目描述

AI识别到面板上有N（1 ≤ N ≤ 100）个指示灯，灯大小一样，任意两个之间无重叠。

由于AI识别误差，每次别到的指示灯位置可能有差异，以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1，右下角x2,y2)，

请输出先行后列排序的指示灯的编号，排序规则：

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

输入描述

第一行为N，表示灯的个数 接下来N行，每行为1个灯的坐标信息，格式为：

编号 x1 y1 x2 y2

• 编号全局唯一
• 1 ≤ 编号 ≤ 100
• 0 ≤ x1 < x2 ≤ 1000
• 0 ≤ y1 < y2 ≤ 1000

输出描述

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

示例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

题解

题目就是一道模拟排序题。

其实就是先按行，再按列进行排序，这里的行不是严格的行（在一定范围内可以认为是同行）。数据量不大可以直接按照题目要求进行模拟得到答案即可。

Java

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;
/**
 * @author code5bug
 */
class Light {
    int no, x1, y1, x2, y2;

    public Light(int no, int x1, int y1, int x2, int y2) {
        this.no = no;
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();

        List<Light> lights = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            int no = scanner.nextInt();
            int x1 = scanner.nextInt();
            int y1 = scanner.nextInt();
            int x2 = scanner.nextInt();
            int y2 = scanner.nextInt();
            lights.add(new Light(no, x1, y1, x2, y2));
        }

        // 指定编号的指示灯是否已选择
        boolean[] selected = new boolean[101];
        // 排序后的编号列表
        List<Integer> sortedRst = new ArrayList<>();

        while (true) {
            // 在尚未排序的灯中挑选最高的灯作为的基准灯
            Light baseLight = null;
            for (Light light : lights) {
                if (selected[light.no]) continue;
                if (baseLight == null || baseLight.y1 > light.y1) {
                    baseLight = light;
                }
            }

            if (baseLight == null) break;

            // 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行
            // （即两个灯坐标的差 ≤ 灯高度的一半）。
            List<int[]> lineLights = new ArrayList<>();
            // 灯半径
            double lightRadius = (baseLight.y2 - baseLight.y1) / 2.0;
            for (Light light : lights) {
                int no = light.no, y1 =