星际篮球争霸赛

描述

星际篮球争霸赛
题目：
在星球争霸篮球赛对抗赛中，最大的宇宙战队希望每个人都能拿到MVP，MVP的条件是单场最高分得分获得者，可以并列。所以宇宙战队决定在比赛中尽可能让更多队员上场，并且让所有得分的选手得分都相同，然而比赛过程中的每1分钟的得分都只能由某一个人包揽。
输入：
输入第一行为一个数字t，表示有得分的分钟数1≤t≤50；
第二行为t个数字，代表每一分钟的得分p,1≤t≤50
输出：
输出有得分的队员都是MVP时，最少得MVP得分

输入

9
5 2 1 5 2 1 5 2 1

输出

6

题解

题目要求所有得分的选手得分都相同，且让更多队员上场，因此我们可以枚举每个可能的得分，计算当前得分下至少需要多少人得分等于该得分，然后取最小值即可。

具体实现时，我们可以使用哈希表来记录每个得分出现的次数，然后从得分最高的开始枚举，计算在当前得分下至少需要多少人得分等于该得分，具体计算方法是先将得分高于当前得分的所有得分都减去1，然后将得分等于当前得分的人数减去1，直到所有得分都等于当前得分为止，这时需要得分等于当前得分的人数即为至少需要得分为当前得分的人数。最后将所有可能的得分下所需人数取最小值即为最少需要得分为MVP的得分。

C++代码

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

int main() {
    int t;
    cin >> t;
    unordered_map<int, int> cnt; // 哈希表，记录每个得分出现的次数
    int max_score = 0; // 最高得分
    for (int i = 0; i < t; ++i) {
        int score;
        cin >> score;
        max_score = max(max_score, score);
        ++cnt[score];
    }
    int ans = t; // 最少需要得分为MVP的得分，初始化为总得分数
    for (int score = max_score; score >= 1; --score) { // 从最高得分开始枚举
        if (cnt[score] == 0) { // 如果当前得分未出现过，则直接跳过
            continue;
        }
        int sum = 0; // 至少需要得分为当前得分的人数
        for (int i = max_score; i > score; --i) { // 处理高于当前得分的得分
            sum += cnt[i]; // 把高于当前得分的得分都减去1，即不需要得分为当前得分的人
            cnt[i - 1] += cnt[i]; // 把高于当前得分的得分都减去1，即不需要得分为当前得分的人
        }
        sum += cnt[score] - 1; // 把得分等于当前得分的人数减去1，至少需要得分为当前得分的人数
        ans = min(ans, sum); // 取最小值
    }
    cout << ans << endl;
    return 0;
}