题目分析

题目要求对识别到的 N 个指示灯进行排序，排序规则是先行后列。由于 AI 识别误差，指示灯的位置可能有偏差。需要按照以下规则排序：

1. 行排序：每次从未排序的灯中选择最高的灯作为基准灯，找到与其在同一行的所有灯。两个灯的纵向中心坐标差不超过基准灯高度的一半，则认为在同一行。

2. 列排序：在同一行的灯，按照横向中心坐标从小到大排序。

解题思路

1. 数据预处理：读取所有指示灯的信息，计算每个灯的中心坐标（x_center, y_center）和高度（height）。

2. 排序过程：

   • 初始化未排序灯集合。

   • 循环：

     • 从未排序的灯中找到最高的灯（y_center 最小）。
     • 将其作为基准灯，计算其高度的一半（half_height）。
     • 遍历未排序的灯，找到与基准灯在同一行的灯（abs(y_center - base_y_center) ≤ half_height）。
     • 将这些灯按照x_center从小到大排序。
     • 将排序后的灯编号添加到结果列表中，并从未排序集合中移除。

3. 输出结果：按照排序后的编号列表输出。

cpp

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

struct Light {
    int id;
    double x_center;
    double y_center;
    double height;
    bool placed;
};

int main() {
    int N;
    std::cin >> N;
    std::vector<Light> lights(N);

    for (int i = 0; i < N; ++i) {
        int id;
        double x1, y1, x2, y2;
        std::cin >> id >> x1 >> y1 >> x2 >> y2;

        lights[i].id = id;
        lights[i].x_center = (x1 + x2) / 2.0;
        lights[i].y_center = (y1 + y2) / 2.0;
        lights[i].height = y2 - y1;
        lights[i].placed = false;
    }

    std::vector<int> result;

    while (true) {
        // 查找未放置的灯
        std::vector<Light*> unplaced_lights;
        for (auto& light : lights) {
            if (!light.placed) {
                unplaced_lights.push_back(&light);
            }
        }

        if (unplaced_lights.empty()) {
            break;
        }

        // 找到最高的灯（y_center 最小）
        auto base_light = *std::min_element(unplaced_lights.begin(), unplaced_lights.end(),
            [](Light* a, Light* b) {
                return a->y_center < b->y_center;
            });

        double base_y_center = base_light->y_center;
        double half_height = base_light->height / 2.0;

        // 找到与基准灯在同一行的灯
        std::vector<Light*> same_row_lights;
        for (auto& light_ptr : unplaced_lights) {
            if (std::abs(light_ptr->y_center - base_y_center) <= half_height) {
                same_row_lights.push_back(light_ptr);
            }
        }

        // 按 x_center 从小到大排序
        std::sort(same_row_lights.begin(), same_row_lights.end(),
            [](Light* a, Light* b) {
                return a->x_center < b->x_center;
            });

        // 添加到结果并标记为已放置
        for (auto& light_ptr : same_row_lights) {
            result.push_back(light_ptr->id);
            light_ptr->placed = true;
        }
    }

    // 输出结果
    for (size_t i = 0; i < result.size(); ++i) {
        std::cout << result[i];
        if (i != result.size() - 1) {
            std::cout << " ";
        }
    }

    return 0;
}

python

N = int(input())
lights = []

for _ in range(N):
    tokens = input().split()
    id = int(tokens[0])
    x1, y1, x2, y2 = map(float, tokens[1:])
    x_center = (x1 + x2) / 2.0
    y_center = (y1 + y2) / 2.0
    height = y2 - y1
    lights.append({
        'id': id,
        'x_center': x_center,
        'y_center': y_center,
        'height': height,
        'placed': False
    })

result = []

while True:
    unplaced_lights = [light for light in lights if not light['placed']]
    if not unplaced_lights:
        break

    # 找到最高的灯
    base_light = min(unplaced_lights, key=lambda l: l['y_center'])
    base_y_center = base_light['y_center']
    half_height = base_light['height'] / 2.0

    # 找到同一行的灯
    same_row_lights = []
    for light in unplaced_lights:
        if abs(light['y_center'] - base_y_center) <= half_height:
            same_row_lights.append(light)

    # 按 x_center 排序
    same_row_lights.sort(key=lambda l: l['x_center'])

    # 添加到结果并标记为已放置
    for light in same_row_lights:
        result.append(light['id'])
        light['placed'] = True

# 输出结果
print(' '.join(map(str, result)))

java

import java.util.*;

public class Main {
    static class Light {
        int id;
        double x_center;
        double y_center;
        double height;
        boolean placed;

        public Light(int id, double x_center, double y_center, double height) {
            this.id = id;
            this.x_center = x_center;
            this.y_center = y_center;
            this.height = height;
            this.placed = false;
        }
    }

    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 id = scanner.nextInt();
            double x1 = scanner.nextDouble();
            double y1 = scanner.nextDouble();
            double x2 = scanner.nextDouble();
            double y2 = scanner.nextDouble();
            double x_center = (x1 + x2) / 2.0;
            double y_center = (y1 + y2) / 2.0;
            double height = y2 - y1;
            lights.add(new Light(id, x_center, y_center, height));
        }

        List<Integer> result = new ArrayList<>();

        while (true) {
            List<Light> unplaced_lights = new ArrayList<>();
            for (Light light : lights) {
                if (!light.placed) {
                    unplaced_lights.add(light);
                }
            }

            if (unplaced_lights.isEmpty()) {
                break;
            }

            // 找到最高的灯
            Light base_light = Collections.min(unplaced_lights, Comparator.comparingDouble(l -> l.y_center));
            double base_y_center = base_light.y_center;
            double half_height = base_light.height / 2.0;

            // 找到同一行的灯
            List<Light> same_row_lights = new ArrayList<>();
            for (Light light : unplaced_lights) {
                if (Math.abs(light.y_center - base_y_center) <= half_height) {
                    same_row_lights.add(light);
                }
            }

            // 按 x_center 排序
            same_row_lights.sort(Comparator.comparingDouble(l -> l.x_center));

            // 添加到结果并标记为已放置
            for (Light light : same_row_lights) {
                result.add(light.id);
                light.placed = true;
            }
        }

        // 输出结果
        for (int i = 0; i < result.size(); i++) {
            System.out.print(result.get(i));
            if (i != result.size() - 1) {
                System.out.print(" ");
            }
        }
    }
}

题目内容

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

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

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

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

输入描述

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

编号 $x_1$ $y_1$ $x_2$ $y_2$

编号全局唯一

• $1 ≤$ 编号 $≤ 100$

• $0 ≤ x_1 < x_2 ≤ 1000$

• $0 ≤ y_1 < y_2 ≤ 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

说明