问题陈述

AtCoder 乐园的一家纪念品商店出售 $N$ 盒子。

这些盒子的编号为 $1$ 至 $N$ ，盒子 $i$ 的价格为 $A_i$ 日元，里面有 $A_i$ 块糖果。

高桥想买下 $N$ 盒中的 $M$ ，并给 $M$ 个名叫 $1, 2, \ldots, M$ 的人每人一盒。

在这里，他想买的盒子要满足以下条件：

• 对于每个 $i = 1, 2, \ldots, M$ 人， $i$ 都能得到至少装有 $B_i$ 粒糖果的盒子。

请注意，不允许给一个人多个盒子，也不允许给多个人同一个盒子。

求是否可能买到满足条件的 $M$ 盒，如果可能，求高桥需要支付的最小总金额。

#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;

typedef long long LL;

const int N = 2e5+10;

int a[N],b[N];
int p[N];

typedef long long LL;

LL ans;

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    //排序完找单调性，找关系
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    int p=1;
    for(int i=1;i<=m;i++)
    {
        while(p<=n&&a[p]<b[i]) p++;
        if(p>n)
        {
            cout<<"-1";
            return 0;
        }
        ans+=a[p];
        p++;
    }
    cout<<ans;
    return 0;
}

//二分
//将a,b排序，b[i]一定大于等于b[i-1]
//b[i-1]占据一点，因此l必然在b[i-1]占据点右侧
//从b[i]占据点右侧分从而避免重复
#include<iostream>
#include<algorithm>
#include<unordered_map>

using namespace std;

typedef long long LL;

const int N = 2e5+10;

int a[N],b[N];
int p[N];

typedef long long LL;

LL ans;

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++) cin>>b[i];
    sort(a+1,a+1+n);
    sort(b+1,b+1+m);
    int last=1;
    for(int i=1;i<=m;i++)
    {
        int l=last,r=n+1;
        while(l<r)
        {
            int mid=l+r>>1;
            if(a[mid]>=b[i]) r=mid;
            else l=mid+1;
        }
        if(l==n+1)//预留不满足点
        {
            cout<<"-1";
            return 0;
        }
        ans+=a[l];
        last=l+1;
    }
    cout<<ans;
    return 0;
}