AI面板识别
AI面板识别
真题目录: 点击去查看
E 卷 100分题型
题目描述
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
输出描述
排序后的编号列表，编号之间以空格分隔。
用例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
说明
题解
思路：
- 将所有灯按照y1升序排序(方法有直接排序或者优先队列都可以)
- 循环遍历，根据条件(两个灯高低偏差不超过灯半径算同一行) 处理一行数据。
- 如果当前行只有一个数据，直接输出
- 多个数据需要按照x进行排序，排序之后按照顺序进行输出
c++
#include <cerrno>
#include <iostream>
#include<queue>
#include <vector>
#include<algorithm>
using namespace std;
struct Item {
int id;
int x;
int y;
bool operator<(const Item& other) const {
return y > other.y;
}
};
bool cmp(Item i1, Item i2) {
return i1.x < i2.x;
}
int main() {
int n;
cin >> n;
// 使用优先队列进行y的升序排序
priority_queue<Item> pq;
double height;
for (int i = 0; i < n; i++) {
int id;
int x1, x2, y1, y2;
cin >> id >> x1 >> y1 >> x2 >> y2;
pq.push({id, x1, y1});
height = (y2 - y1 * 1.0) / 2;
}
while (!pq.empty()) {
Item first = pq.top();
pq.pop();
// 当前行只有一个元素
if (pq.empty() || pq.top().y - first.y > height) {
cout << first.id << " ";
} else {
vector<Item> ans;
ans.push_back(first);
// 迭代获取所有行
while (!pq.empty() && pq.top().y - first.y <= height) {
Item tmp = pq.top();
pq.pop();
ans.push_back(tmp);
}
// 按照行进行排序
sort(ans.begin(), ans.end(), cmp);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i].id << " ";
}
}
}
return 0;
}
JAVA
import java.util.*;
class Item implements Comparable<Item> {
int id;
int x;
int y;
Item(int id, int x, int y) {
this.id = id;
this.x = x;
this.y = y;
}
@Override
public int compareTo(Item other) {
// 按 y 升序排序
return Integer.compare(this.y, other.y);
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
PriorityQueue<Item> pq = new PriorityQueue<>();
double height = 0;
for (int i = 0; i < n; i++) {
int id = scanner.nextInt();
int x1 = scanner.nextInt();
int y1 = scanner.nextInt();
int x2 = scanner.nextInt();
int y2 = scanner.nextInt();
pq.add(new Item(id, x1, y1));
height = (y2 - y1) * 0.5;
}
while (!pq.isEmpty()) {
Item first = pq.poll();
// 当前行只有一个元素
if (pq.isEmpty() || pq.peek().y - first.y > height) {
System.out.print(first.id + " ");
} else {
List<Item> ans = new ArrayList<>();
ans.add(first);
// 迭代获取所有行的元素
while (!pq.isEmpty() && pq.peek().y - first.y <= height) {
ans.add(pq.poll());
}
// 按 x 升序排序
ans.sort(Comparator.comparingInt(o -> o.x));
for (Item item : ans) {
System.out.print(item.id + " ");
}
}
}
scanner.close();
}
}
Python
import heapq
class Item:
def __init__(self, id, x, y):
self.id = id
self.x = x
self.y = y
def __lt__(self, other):
# 按 y 升序排序
return self.y < other.y
def main():
n = int(input())
pq = [] # 使用 heapq 实现优先队列
height = 0
for _ in range(n):
id, x1, y1, x2, y2 = map(int, input().split())
heapq.heappush(pq, Item(id, x1, y1))
height = (y2 - y1) * 0.5
while pq:
first = heapq.heappop(pq)
# 当前行只有一个元素
if not pq or pq[0].y - first.y > height:
print(first.id, end=" ")
else:
ans = [first]
# 迭代获取所有行的元素
while pq and pq[0].y - first.y <= height:
ans.append(heapq.heappop(pq))
# 按 x 升序排序
ans.sort(key=lambda item: item.x)
for item in ans:
print(item.id, end=" ")
if __name__ == "__main__":
main()
JavaScript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
class Item {
constructor(id, x, y) {
this.id = id;
this.x = x;
this.y = y;
}
}
function main() {
let n; // 输入的数量
const pq = []; // 存储所有的项目
let height = 0; // 高度变量
let inputLines = []; // 用于存储所有输入
rl.on('line', (input) => {
inputLines.push(input); // 收集每一行输入
// 当接收到 n + 1 行时，停止输入并开始处理
if (inputLines.length === 1) {
n = parseInt(inputLines[0]); // 第一行是数量
} else if (inputLines.length === n + 1) {
// 解析输入数据
for (let i = 1; i <= n; i++) {
const [id, x1, y1, x2, y2] = inputLines[i].split(' ').map(Number);
pq.push(new Item(id, x1, y1));
height = (y2 - y1) * 0.5; // 计算高度
}
// 按 y 升序排序
pq.sort((a, b) => a.y - b.y);
// 开始处理项目
while (pq.length > 0) {
const first = pq.shift(); // 取出队列中的第一个元素， 基准元素
// 当前行只有一个元素
if (pq.length === 0 || pq[0].y - first.y > height) {
process.stdout.write(first.id + " ");
} else {
const ans = [first]; // 存储当前行的所有元素
// 收集当前行的所有元素
while (pq.length > 0 && pq[0].y - first.y <= height) {
ans.push(pq.shift());
}
// 按 x 升序排序
ans.sort((a, b) => a.x - b.x);
// 输出当前行的所有元素 ID
for (let item of ans) {
process.stdout.write(item.id + " ");
}
}
}
rl.close(); // 所有数据处理完毕后，关闭输入流
}
});
}
main();
Go
package main
import (
"fmt"
"sort"
)
type Item struct {
id int
x int
y int
}
func main() {
var n int
fmt.Scan(&n)
items := make([]Item, n)
var height float64
// 输入数据
for i := 0; i < n; i++ {
var id, x1, x2, y1, y2 int
fmt.Scan(&id, &x1, &y1, &x2, &y2)
height = float64(y2-y1) / 2
items[i] = Item{id: id, x: x1, y: y1}
}
// 按照 y 升序排序
sort.Slice(items, func(i, j int) bool {
return items[i].y < items[j].y
})
for len(items) > 0 {
first := items[0]
items = items[1:]
if len(items) == 0 || float64(items[0].y-first.y) > height {
// 当前行只有一个元素
fmt.Printf("%d ", first.id)
} else {
// 收集同一行的元素
group := []Item{first}
for len(items) > 0 && float64(items[0].y-first.y) <= height {
group = append(group, items[0])
items = items[1:]
}
// 按 x 排序
sort.Slice(group, func(i, j int) bool {
return group[i].x < group[j].x
})
for _, item := range group {
fmt.Printf("%d ", item.id)
}
}
}
}