当前位置：首页 > article >正文

东方博宜24年12月-B组（才俊）- 重铠马的选择

article 2025/1/10 2:24:43

题目描述

在潘多拉星球的草原上，纳美族正在举行一场隆重的仪式——重铠马的选择仪式。
每匹重铠马都会站在固定的位置挑选自己的主人，主人也必须站在固定的位置等待重铠马的选择。
现场共有 N 位候选人（编号 1∼N），每位候选人的位置为 (PXi ,PYi )，同时有 M 匹重铠马（编号 1∼M），它们的初始位置为 (HXj ,HYj )。
每匹重铠马按照编号 1∼M 的顺序，依次选择与自己距离最近，且没有被其他重铠马选中的候选人作为自己主人。如果有多位候选人与某匹重铠马的距离相同，则重铠马会优先选择编号较小的候选人。
然而，由于重铠马数量有限，一些候选人可能无法被任何重铠马选中。
你的任务是编程找出所有未被重铠马选中的候选人编号，并按编号从小到大的顺序输出。

输入
第一行包含两个整数 N 和 M，分别表示候选人的数量和重铠马的数量。
接下来的 N 行，每行包含两个整数 PXi 和 PYi ，表示第 i 位候选人的位置。
再接下来的 M 行，每行包含两个整数 HXj 和 HYj ，表示第 j 匹重铠马的初始位置。

输出
输出若干行，每行一个整数，按照从小到大的顺序，依次输出未被重铠马选中的候选人编号。
如果所有候选人都被选中，则输出 0。

样例
输入
3 2
1 0
3 1
2 1
1 1
1 2
输出
2
输入
9 5
-1 2
6 -2
3 0
6 8
-5 3
8 -2
-6 7
3 -3
3 -5
-2 9
-10 -1
-7 1
1 2
8 6
输出
2
6
8
9
输入
18 6
1 7
1 4
-10 10
12 0
8 -2
-2 6
1 10
6 1
7 3
8 9
10 10
-6 4
1 10
-3 4
3 -2
-10 0
9 -3
9 -1
-7 5
10 2
4 7
8 -1
-8 -8
8 -8
输出
2
3
6
7
8
9
10
11
13
14
15
18

说明
样例 1 说明
有 3 个人，2 匹马。
1 号马到编号为 1 和编号为 3 的人都是最近的，按照规则，它将选择 1 号做主人。
2 号马选择离它最近的 3 号做主人。
因此编号为 2 的人未被任何重铠马选中。

提示
在解决问题时，需要计算重铠马与候选人之间的距离，假设求第 j 匹重铠马和第 i 个人之间的距离，则求解公式为：d(j,i)= 根号下【(HXj −PXi )^2 +(HYj −PYi )^2】。
数据范围
测试点 1 满足 M=N。
测试点 2 满足 M=1,N=5。
测试点 3∼4 满足 1≤M≤N≤20。
测试点 6∼10 满足 1≤M≤N≤1000，−10^6 ≤PXi ,PYi ,HXj ,HYj ≤10^6 。

分析

为了找到未被重铠马选中的候选人，我们可以按照以下步骤进行编程实现：

输入处理：首先读取候选人和重铠马的数量以及它们的位置。
距离计算：使用欧几里得距离公式计算每匹重铠马与所有候选人之间的距离。
选择规则：每匹重铠马依次选择最近的候选人，如果有多个候选人距离相同，则选择编号较小的候选人。
记录未被选中的候选人：在所有重铠马选择完后，输出所有未被选中的候选人编号。

代码

下面是实现该逻辑的 C++ 代码：

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

using namespace std;

struct Candidate {
    int id;
    int x, y;
    bool selected = false; // 标记是否被选中
};

struct Horse {
    int x, y;
};

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

    vector<Candidate> candidates(N);
    vector<Horse> horses(M);

    // 输入候选人位置
    for (int i = 0; i < N; ++i) {
        candidates[i].id = i + 1; // 编号从1开始
        cin >> candidates[i].x >> candidates[i].y;
    }

    // 输入重铠马位置
    for (int j = 0; j < M; ++j) {
        cin >> horses[j].x >> horses[j].y;
    }

    // 每匹重铠马选择候选人
    for (int j = 0; j < M; ++j) {
        int closestIndex = -1;
        double minDistance = numeric_limits<double>::max();

        for (int i = 0; i < N; ++i) {
            // 跳过已经被选中的候选人
            if (candidates[i].selected) continue;

            // 计算距离
            double distance = sqrt(pow(horses[j].x - candidates[i].x, 2) + 
                                   pow(horses[j].y - candidates[i].y, 2));
            
            // 选择最近的候选人
            if (distance < minDistance || 
                (distance == minDistance && candidates[i].id < candidates[closestIndex].id)) {
                closestIndex = i;
                minDistance = distance;
            }
        }

        // 如果找到了最近的候选人，标记为被选中
        if (closestIndex != -1) {
            candidates[closestIndex].selected = true;
        }
    }

    // 输出未被选中的候选人
    vector<int> unselected;
    for (const auto& candidate : candidates) {
        if (!candidate.selected) {
            unselected.push_back(candidate.id);
        }
    }

    if (unselected.empty()) {
        cout << 0 << endl; // 所有候选人都被选中
    } else {
        // 按照编号从小到大输出
        sort(unselected.begin(), unselected.end());
        for (int id : unselected) {
            cout << id << endl;
        }
    }

    return 0;
}

程序说明：

结构体定义：
- Candidate 结构体用于存储候选人的信息，包括编号、坐标和选中状态。
- Horse 结构体用于存储重铠马的位置。
输入：
- 读取候选人和重铠马的位置，并存储到相应的结构体中。
选择逻辑：
- 对于每匹重铠马，遍历所有候选人，计算距离并根据规则选择最近的候选人。
- 使用 selected 标记候选人是否被选中，确保每个候选人只能被选择一次。
输出未被选中的候选人：
- 遍历所有候选人，输出未被选中的候选人编号，如果没有未被选中的候选人，则输出 0。