PAT L1 - 056 猜数字

时间:2022-08-18 19:35:53

https://pintia.cn/problem-sets/994805046380707840/problems/994805074646122496

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

输入格式:

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

输出格式:

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

输入样例:

7
Bob 35
Amy 28
James 98
Alice 11
Jack 45
Smith 33
Chris 62

输出样例:

22 Amy

时间复杂度:$O(n \log(n))$

代码:
#include <bits/stdc++.h>
using namespace std; struct Stu {
char name[50];
int num;
double ans;
}s[11111]; bool cmp(const Stu& a, const Stu& b) {
return a.ans < b.ans;
} int main() {
int n;
scanf("%d", &n);
double sum = 0, ave = 0;
for(int i = 1; i <= n; i ++) {
scanf("%s %d", s[i].name, &s[i].num);
sum += s[i].num;
} ave = 1.0 * sum / n;
ave /= 2.0; for(int i = 1; i <= n; i ++)
s[i].ans = abs(s[i].num - ave); sort(s + 1, s + 1 + n, cmp);
printf("%.0lf %s\n", ave, s[1].name); return 0;
}