卡卡西排座位2017包河

Question

卡卡西排座位
描述
卡卡西的班主任鸣人在教学管理方面有自己的一套独特的方法。就比如，同样是安排座位，他们班级的做法就非常与众不同。具体做法是这样的：班级的n个同学按照序号依次将自己期望的同桌序号写在纸上，统一交由鸣人。鸣人进行统计，按照得票数从高到低的顺序，先安排得票高的同学的同桌，如果该同桌未被安排，则安排给对应同学，如果已经被安排了，则按照序号从头挑选没有安排同桌的同学。

输入
2行，

第一行班级人数n，

第二行按照序号依次给出每一个同学期望的同桌的序号。

输出
n行，每行两个数字，中间用空格隔开，第一个数是序号，第二个数是该序号同学同桌的序号。

输入样例 1
8
3 3 4 6 6 8 2 3
输出样例1
1 2
2 1
3 4
4 3
5 7
6 8
7 5
8 6
提示
样例解释：

有3个人想跟3号坐，3号第一个选择，选择4号；有2个人想跟6号坐，6号第二个选择，选择8号；有1个人想跟2号坐，2号第三个选择，因为3号已经被选择，所以2号只能选择1号；余下5号和7号正好同桌。

数据范围：

n是偶数，且4<=n<=50。

说明：

如果两人得票数一样，序号小的人先选。

Answer 1

以下内容由CHATGPT及阿里嘎多学长共同生成、有用望采纳：

---

这个问题是一个编程问题，具体是关于如何根据给定的规则来安排班级座位。以下是问题的具体描述和解决方案的概述：

问题描述

• 班级里有 n 个同学。
• 每个同学都有一个期望的同桌序号，这些序号被写在纸上并提交给班主任鸣人。
• 鸣人需要根据得票数从高到低的顺序安排座位。如果一个同学的期望同桌已经被安排了，则选择下一个未被安排的同学作为同桌。
• 如果两人得票数一样，序号小的人先选。

输入

• 第一行：班级人数 n
• 第二行：每个同学期望的同桌序号，序号从1开始。

输出

• n 行，每行两个数字，中间用空格隔开，表示每个同学的序号和他们同桌的序号。

示例

• 输入样例 1：

  8
  3 3 4 6 6 8 2 3
  

• 输出样例 1：

  1 2
  2 1
  3 4
  4 3
  5 7
  6 8
  7 5
  8 6
  

解决方案概述

1. 读取输入：首先读取班级人数 n 和每个同学期望的同桌序号。
2. 统计得票数：创建一个数组来统计每个同学被选择的次数。
3. 安排座位：按照得票数从高到低的顺序，安排每个同学的同桌。如果期望的同桌已经被安排了，选择下一个未被安排的同学。
4. 输出结果：输出每个同学的序号和他们同桌的序号。

代码实现

以下是使用 C++ 语言实现的代码示例：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> votes(n + 1, 0); // 投票数统计
    vector<int> pairs(n + 1, 0); // 同桌安排
    vector<int> candidates; // 待安排的同学

    // 读取每个同学期望的同桌序号
    for (int i = 1; i <= n; i++) {
        int desired;
        cin >> desired;
        votes[desired]++;
        candidates.push_back(i);
    }

    // 按得票数排序，得票数相同则序号小的在前
    sort(candidates.begin(), candidates.end(), [&votes](int a, int b) {
        return votes[a] == votes[b] ? a < b : votes[a] > votes[b];
    });

    // 安排座位
    for (int i : candidates) {
        int desired = i;
        while (pairs[desired] != 0) {
            desired = desired % n + 1; // 从1开始循环
        }
        pairs[i] = desired;
        pairs[desired] = i;
    }

    // 输出结果
    for (int i = 1; i <= n; i++) {
        cout << i << " " << pairs[i] << endl;
    }

    return 0;
}

这段代码首先统计每个同学的得票数，然后根据得票数和序号从高到低的顺序安排座位，最后输出每个同学的序号和他们同桌的序号。