AI面板识别 - 华为OD机试题

输入：
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

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

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

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 = light.y1;
                if (selected[no]) continue;
                if (y1 - baseLight.y1 <= lightRadius) {
                    lineLights.add(new int[]{light.x1, no});
                }
            }

            // 同一行，按照列进行排序
            lineLights.sort(Comparator.comparingInt(a -> a[0]));
            for (int[] light : lineLights) {
                int no = light[1];
                selected[no] = true;
                sortedRst.add(no);
            }
        }

        // 打印排序结果
        for (int no : sortedRst) {
            System.out.print(no + " ");
        }
    }
}