A25145. 小球的重量
填空题
容易
知识点
题目描述
小球的重量
题目描述：
有 n 个小球，编号为 1 到 n，所有小球的重量均不相等。
按照编号顺序，依次给出 1 到 n - 1 号小球与其他小球的重量比较关系（< 表示小于，> 表示大于）。
请找出重量第 k 大的小球，并输出其编号。
例如：n = 4，有 4 个小球，比较关系如下：
1 号小球与 2、3、4 号小球的重量比较关系：小于 2 号，小于 3 号，大于 4 号；用 "< < >" 表示。
2 号小球与 3、4 号小球的重量比较关系：大于 3 号，大于 4 号；用 "> >" 表示。
3 号小球与 4 号小球的重量比较关系：大于 4 号；用 ">" 表示。
根据上述比较关系可得，按照重量由大到小排序后小球的编号分别为：2、3、1、4；当 k = 3 时，重量第 3 大的小球编号为 1。
输入描述：
共 n + 1 行；
第一行输入一个整数 n（1≤n≤2000），表示小球的数量；
第二行输入 n - 1 个字符，字符为 '>' 或 '<'，依次表示 1 号小球与 2、3、...、n 号小球的重量比较关系；
第三行输入 n - 2 个字符，字符为 '>' 或 '<'，依次表示 2 号小球与 3、4、...、n 号小球的重量比较关系；
... 第 n 行输入 1 个字符，字符为 '>' 或 '<'，表示 n - 1 号小球与 n 号小球的重量比较关系；
以上输入中，同一行字符之间以一个空格隔开；
第 n + 1 行输入一个整数 k（1≤k≤n）。
输出描述：
输出一个整数，表示重量第 k 大的小球编号。
样例输入：
4
< < >
> >
>
3样例输出：
1参考答案
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<char>> comp(n, vector<char>(n, 0));
// 读取并构建比较矩阵
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
cin >> comp[i][j];
comp[j][i] = (comp[i][j] == '<') ? '>' : '<';
}
}
// 计算比每个球重的数量
vector<int> heavierCount(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i != j && comp[i][j] == '<') {
heavierCount[i]++;
}
}
}
int k;
cin >> k;
for (int i = 0; i < n; i++) {
if (heavierCount[i] == k - 1) {
cout << i + 1;
break;
}
}
return 0;
}答案解析
构建比较矩阵，填充对称关系
统计比每个小球重的数量
第k大的小球满足：比它重的数量 = k-1
上一题
下一题