GPLTL1056 猜数字

原题链接：GPLTL1056 猜数字

题目

一群人坐在一起，每人猜一个 $100$ 以内的数，谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。

输入格式：

输入在第一行给出一个正整数 $N(≤10^4)$。随后 N 行，每行给出一个玩家的名字（由不超过8个英文字母组成的字符串）和其猜的正整数 $(≤ 100)$。

输出格式：

在一行中顺序输出：大家平均数的一半（只输出整数部分）、赢家的名字，其间以空格分隔。题目保证赢家是唯一的。

输入样例：

7

Bob 35

Amy 28

James 98

Alice 11

Jack 45

Smith 33

Chris 62

输出样例：

22 Amy

题解

读取数据：首先读入正整数 $N$，由于 $N(≤10^4)$，所以直接用 int 存储。

int n; cin >> n;

因为需要计算大家平均数的一半，所以声明一个变量用于对所有猜测的数字进行求和。注意到 $N(≤10^4)$，且每个人猜的正整数 $(≤ 100)$，所以最终的和 $S <= 10^6 < 10^9$，可以使用 int 类型保存。

int sum = 0;

随后声明一个 std::vector (动态数组) 用来保存猜测者名字和猜测的数字，可以通过声明一个结构体来帮助组织数据：

struct Player {
    string name; // 名字
    int num; // 猜测的数字
};

vector<Player> memo(n); // 保存信息的数组 初始化长度为 n

或者更简单一点，使用 std::pair 来保存这样的结构：

vector<pair<string, int>> memo(n);

然后依次读入数据，并加和：

for (int i = 0; i < n; ++i) {
    string name; int num;
    cin >> name >> num;
	
    // 语法糖 等价于 memo[i] = pair<string, int>{name, num};
    memo[i] = {name, num};
    
    sum += num;
}

或者使用 范围 for 语法：

// auto 让编译器帮助自动推断类型
// & 表示引用，参考：https://zh.cppreference.com/w/cpp/language/reference
for (auto& player : memo) {
    cin >> player.first >> player.second;
    sum += player.second;
}

计算目标值：然后计算大家平均数的一半

double target = sum * 1.0 / n / 2;
// 或者
double target = sum * 1.0 / memo.size() / 2;
// memo.size() 返回数组长度，即 n

这里我们将总和 sum 转换为浮点数，然后除以玩家数量 n，再除以 2，得到大家平均数的一半。

寻找最接近目标值的玩家： 我们需要遍历所有玩家，计算每个玩家的猜测值与目标值之间的差距，并找到差距最小的玩家。

double diff = 100; // 最大差值不可能超过 100，所以选取 100 作为初始差值
string winner;

for (auto& player : memo) {
    double this_diff = fabs(player.second - target);
    if (this_diff < diff) {
        winner = player.first;
        diff = this_diff;
    }
}

在这个循环中，我们使用 abs 函数计算每个玩家的猜测值与目标值之间的绝对差距。如果当前差距小于之前记录的最小差距，我们更新最小差距并记录当前玩家的名字。

输出结果： 最后，我们输出目标值的整数部分和赢家的名字。

cout << static_cast<int>(target) << ' ' << winner << '\n';

AC 代码

#include <bits/stdc++.h> // 万能头文件

using namespace std;

int main() {
    int n; cin >> n;
    int sum = 0;
    vector<pair<string, int>> memo(n);
    
    for (auto& player : memo) {
        cin >> player.first >> player.second;
        sum += player.second;
    }
    
    double target = sum * 1.0 / n / 2;
    
    double diff = 100; // 储存当前最小差值 最大差值不可能超过 100，所以选取 100 作为初始差值
    string winner; // 存储当前最接近目标值玩家的名字

    for (auto& player : memo) {
        double this_diff = fabs(player.second - target);
        if (this_diff < diff) {
            winner = player.first;
            diff = this_diff;
        }
    }
    
    cout << static_cast<int>(target) << ' ' << winner << '\n';
    
    return 0;
}