题解 LOPOV - Lopov

· · 题解

解题思路

背包？不不不，这显然是一道贪心。

我们要求的是能获得的最大价值，因此我们先以价值排序。对于一个质量为 M 的珠宝，我们将其装进一个容量大于 M 的袋子中容量最小的袋子显然最优（因为已经按照价值排序）。然后我们考虑怎么找到合适的袋子。

  1. 暴力找，时间复杂度 \mathcal O(NK)，不多讲，一个一个扫，显然是不可取的。

  2. 常规二分,对于每个珠宝，二分找上文所说的最优的袋子，但每个袋子只能用一次，所以时间复杂度可能被卡到 \mathcal O(NK)，蒟蒻开始也这么想的（找到一个答案后向上查找第一个没被用过的），但是被机房大佬卡了 qwq。

  3. 可重集，STL 里自带的一种容器 multiset，一个可以有重复元素的集合，由于底层是红黑树，因此无论是删除还是查找复杂度都很优秀（肯定不会超过 \mathcal O(\log K)），因此时间复杂度为 \mathcal O(\log K)，10^6 数据可过。

#include<bits/stdc++.h>
using namespace std;
namespace TO
{
    const int N=1e6+21;
    int n,k;
    long long ans;
    struct node
    {
        int v,m;
    }au[N];
    int cc;
    multiset <int> c;
    bool cmp(node x,node y)
    {
        return x.v>y.v;
    }
    int mian()
    {
        cin>>n>>k;
        for(int i=1;i<=n;i++)
            cin>>au[i].m>>au[i].v;
        for(int i=1;i<=k;i++)
        {
            cin>>cc;
            c.insert(cc);
        }
        sort(au+1,au+1+n,cmp);
        for(int i=1;i<=n;i++)
        {
            auto it=c.lower_bound(au[i].m);
            if(it==c.end())
                continue;
            else
                c.erase(it);
            ans+=au[i].v;
        }
        cout<<ans<<'\n';
        return 0;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    return TO::mian();
}