【Coding】寒假每日一题Day.5.平均

题目来源

题目来自于AcWing平台：https://www.acwing.com/problem/content/5398/
以blog的形式记录程序设计算法学习的过程，仅做学习记录之用。

题目描述

输入输出格式与数据范围

样例

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

27

思路

思路参考自题解：https://www.acwing.com/solution/content/220905/。

这道题是一个贪心的问题，思路非常的简单。我们不需要真的将$n$个数进行存储，认真读题可以发现，$n$是$10$的倍数，并且这$n$个数中的每一个数必定在区间$[0,9]$。因此，实际上只需要维护一个二维数组（一个$vector$数组，使用$push\_back$存储当前数的代价），二维数组第一维是$[0,9]$而第二维是这$10$个数改变它们的代价。

首先对二维数组中每个数组$[0,9]$的代价按照升序排序（使用$sort$快速解决），之后就到了本题最关键的思路：显然，这道题要求每个数出现的次数是$n/10$，这就意味着如果有数的数量小于这个阈值，那么一定需要将别的数改为这个数，等价于这些数不需要进行修改，因为它们本来就不够。

👆而需要修改的数就意味着这个数出现的次数比阈值要多，由于每个数出现的次数都是$n/10$，假设这个数出现$t$次，则需要进行$t?n/10$次修改，修改的当然是这个数中代价最小的那些数，因此这道题变为统计$t?n/10$个代价最小的修改的总和。

Code

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

typedef long long LL;
vector<vector<int> > v(10);

int n, a ,b;

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a >> b;
        v[a].push_back(b);
    }

    for(int i = 0; i < 10; i ++){
        sort(v[i].begin(), v[i].end());
    }

    LL res = 0, c = n / 10;
    for(int i = 0; i < 10; i ++){
        if(v[i].size() < c)   continue;

        for(int j = 0; j < v[i].size - c; j ++){
            res += v[i][j];
        }
    }
    cout << res;
    return 0;
}