题解：CF2036B Startup

· · 题解

题目传送门 1（洛谷 CF2036B）

题目传送门 2（Codeforces 2036B）

我的博客本文链接，欢迎点赞

题目大意

某人有 n 个货架和 k 个瓶子的自动售货机，第 i 个瓶子的品牌指数和售价分别为 b_i,c_i，每个货架上只能放同一种品牌的瓶子任意多个，而且每个瓶子都会被卖掉。求他卖出能获得的最大金额。

题目分析

这是一个比较简单的贪心。

我们可以预先处理出每一种品牌所有的瓶子的总金额，这里可以用一个 unordered_map 来存，把每个 b_i 放在 map 的第一维，然后对于这个 b_i，map 的第二维存总金额。然后可以把第二维的数据存入一个 vector，并对 vector 从大往小排序，这个 vector 的大小记为 s。接着，从大往小取出来前 n 个的总金额（如果 s < n，那么有多少取多少），可以把每个 b_i 的总金额记为 sum_j，答案就是 sum_j 的总和，即 ans=\sum _j^{\min(n,s)}sum_j，其中，ans 为最终的答案。

单组数据的时间复杂度为 O(k+s+s\log s+\min(n,s))，在最坏情况下，s 和 \min(n,s) 都等于 k，所以总的时间复杂度为 O(k \log k)，而本题中保证 1 \le \sum n,\sum k \le 2\times 10^5，可以通过此题。

Code

（码风良好，适宜阅读）

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 50;
struct node{
    int b, c;
}a[N];
void solve()
{
    int n, k;
    cin >> n >> k;
    unordered_map<int, int> mp;
    for(int i = 1; i <= k; i ++)
    {
        cin >> a[i].b >> a[i].c;
        mp[a[i].b] += a[i].c; //把 b 对应的 c 加到 map 中
    }
    vector<int> sum;
    for(auto &i : mp) sum.push_back(i.second); //把 map 中的 c 添加到 sum 中
    sort(sum.rbegin(), sum.rend()); //对 sum 从大到小排序
    long long ans = 0;
    for(int i = 0; i < min(n, (int)sum.size()); i ++)
    {
        ans += sum[i]; //累加答案
    }
    cout << ans << "\n"; //输出
    return ;
}
int main()
{
    cin.tie(0) -> sync_with_stdio(0);
    int T;
    cin >> T;
    while(T--) solve();
    return 0;
}