给你m个bug， 每个bug都有一个复杂度。n个人， 每个人有两个值， 一个是能力值， 当能力值>=bug的复杂度时才可以修复这个bug， 另一个是雇佣他需要的钱，掏一次钱就可以永久雇佣。 然后给你一个金钱总额， 让你在最短的时间的修复这些bugs， 并且给出每个bug是由谁修复的， 一个人一天只能修复一个bug。
首先， 对bug的复杂度由高到低排序， 对人的能力值由高到低排序。 这时候需要二分修复的时间， 假设需要的时间是t， 那么显然， 一个人一共可以修复t个bug， 因为有t天。
在开始之前， 先把能力值大于第一个bug的复杂度的人全都加入一个优先队列中， 队列按价钱由小到大排序。 然后前t个bugs都由队列首的这个人修复， 之后将这个人pop。到第1+t个bug的时候， 把能力值大于第二个复杂度的人全都入队列， 因为人是按能力值大小排序的， 所以之前在队列中的人同样可以修复第二个bug，然后不断这样循环就可以。
如果在过程中队列空了或者是价钱大于了给定的总额， 就直接返回false。
在二分之前先测试一下时间为m的时候是否可行， 如果不可行就直接输出no， 因为这是最长的时间。
#include<bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
struct node
{
int sk, pr, id;
bool operator <(node a) const
{
return pr>a.pr;
}
};
bool cmp(node a, node b) {
return a.sk > b.sk;
}
const int maxn = 1e5+;
int n, m, cost, ans[maxn];
node st[maxn], pro[maxn];
int check(int t) {
int tmpcost = cost;
priority_queue <node> q;
for(int i = , j = ; j<=m; j+=t) {
while(i<=n&&st[i].sk>=pro[j].sk) {
q.push(st[i]);
i++;
}
if(q.empty()) {
return ;
}
tmpcost -= q.top().pr;
for(int tmp = j; tmp<min(j+t, m+); tmp++) {
ans[pro[tmp].id] = q.top().id;
}
if(tmpcost<)
return ;
q.pop();
}
return ;
}
int main()
{
cin>>n>>m>>cost;
for(int i = ; i<=m; i++) {
scanf("%d", &pro[i].sk);
pro[i].id = i;
}
for(int i = ; i<=n; i++) {
scanf("%d", &st[i].sk);
}
for(int i = ; i<=n; i++) {
scanf("%d", &st[i].pr);
st[i].id = i;
}
sort(pro+, pro++m, cmp);
sort(st+, st++n, cmp);
int flag = ;
for(int i = ; i<=n; i++) {
if(st[i].sk>=pro[].sk&&st[i].pr<=cost)
flag = ;
}
if(!flag) {
cout<<"NO"<<endl;
return ;
}
int l = , r = m, ret;
while(l<=r) {
int mid = l+r>>;
if(check(mid)) {
r = mid-;
ret = mid;
}
else
l = mid+;
}
check(r+);
cout<<"YES"<<endl;
for(int i = ; i<=m; i++) {
cout<<ans[i]<<" ";
}
}