题解：P15232 浣熊的快车道

New_Void · 2026-02-08 18:17:57 · 题解

P15232 浣熊的快车道

思路

看到这道题肯定考虑贪心，一定是先选择 a_i 最小的，然后尽可能放多辆车在 a_i 这条道路上，那么可以使 a_i 从小到大排序，b_i 从大到小排序，那么最多能取多少个在这条路呢？不难发现一定是其中的一部分 b_i 满足从第一个到第 i 个之间的 i 个车辆小于等于当前这个 b_i 那么这些车必然可以在当前道路放下，不难想到可以双指针做。

至于无解就是如果拿到最后所有道路都占满了，还有剩余车辆，那么就是无解。

Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N],b[N];
signed 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,greater<int>());
    int sum=0;
    for (int i=1;i<=m;i++) sum+=b[i];
    if (sum<m){
        cout<<-1;
        return 0;
    }
    int ans=0,r=1,cnt=0,idx=1,qwq=0;
    for (int l=1;l<=n;l++){
        while (r<=m && cnt<b[r]) r++,cnt++,ans+=a[l],qwq++;
        cnt=0;
    }
    if (qwq<m) cout<<-1;
    else cout<<ans;
    return 0;
}