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 = 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 + " ");
        }
    }
}

Python

N = int(input())

lights = [tuple(map(int, input().split())) for _ in range(N)]

# 指定编号的指示灯是否已选择
selected = [False] * 101
# 排序后的编号列表
sorted_rst = []

while True:
    # 在尚未排序的灯中挑选最高的灯作为的基准灯
    base_light = None
    for light in lights:
        no, x1, y1, x2, y2 = light
        if selected[no]:
            continue
        if not base_light or base_light[2] > y1:
            base_light = light

    if not base_light:
        break

    # 找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行（即两个灯坐标的差 ≤ 灯高度的一半）。
    line_lights = []
    # 灯半径
    light_radius = (base_light[4] - base_light[2]) / 2
    base_light_y1 = base_light[2]
    for light in lights:
        no, x1, y1, x2, y2 = light
        if selected[no]:
            continue
        if y1 - base_light_y1 <= light_radius:
            line_lights.append((x1, no))

    # 同一行，按照列进行排序
    line_lights.sort()
    for x1, no in line_lights:
        selected[no] = True
        sorted_rst.append(no)

print(*sorted_rst)

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Light {
public:
    int no, x1, y1, x2, y2;

    Light(int no, int x1, int y1, int x2, int y2)
        : no(no), x1(x1), y1(y1), x2(x2), y2(y2) {}
};

int main() {
    int N;
    cin >> N;

    vector<Light> lights;
    for (int i = 0; i < N; i++) {
        int no, x1, y1, x2, y2;
        cin >> no >> x1 >> y1 >> x2 >> y2;
        lights.emplace_back(no, x1, y1, x2, y2);
    }

    // 指定编号的指示灯是否已选择
    vector<bool> selected(101, false);
    // 排序后的编号列表
    vector<int> sortedRst;

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

        if (!baseLight) break;

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

        // 同一行，按照列进行排序
        sort(lineLights.begin(), lineLights.end());
        for (auto& light : lineLights) {
            int no = light.second;
            selected[no] = true;
            sortedRst.push_back(no);
        }
    }

    // 打印排序结果
    for (int no : sortedRst) {
        cout << no << " ";
    }

    return 0;
}

🙏整理题解不易， 如果有帮助到您，请给点个赞 ???? 和收藏 ?，让更多的人看到。🙏🙏🙏