Codeforces 377B . Preparing for the Contest【優先キュー】

テーマ:
m個のバグがあって、n個の学生、各バグは自分の複雑な値があって、各学生は自分の能力の値があって、複雑な値が自分の能力の値より小さいバグを解決することしかできなくて、しかも毎日1個のバグを解決することしかできなくて、しかし各学生はバグを処理して報酬を必要として、報酬がsを超えない情況の下で、最も短い時間の内で、バグをすべて解決することができます.
方法:
まず,すべてのバグを解決できれば,解決の日数は必ず1~mであることを明らかにする.m日で解決できるかどうかを判断し,できなければNOを出力し,次の操作が可能であれば行う.
問題解決に要する日数tを2分列挙し,bugの複雑な値と同級生の能力値を大きい順から小さい順に並べ替えることができる.まず最も複雑なバグを処理し、そのバグを解決できる同級生を優先キューに追加し、これらの同級生の中で最もお金がかかるバグを解決させ、明らかに、この同級生は最大t個のバグを解決することができる.その後、同級生をキューからポップアップします.残りの解決されていないバグを同じ操作で処理します.プロシージャ内のキューが空であるか、sより大きい費用がかかる場合は、直接戻ります.
コード:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define N 100010
using namespace std;
struct aa
{
    int sk,f,id;
    bool operator <(const aa &s)const
    {
        return sk<s.sk;
    }
}stu[N],bug[N];
struct cmp{
    bool operator()(aa &x,aa &y)
    {
        return x.f>y.f;
    }
};
int n,m,s,ans[N];
bool check(int t)
{
    int cur=0;
    priority_queue<aa,vector<aa>,cmp> que;
    for(int i=m-1,j=n-1;i>=0;i-=t)
    {
        for(;j>=0 && stu[j].sk>=bug[i].sk;j--) que.push(stu[j]);
        if(que.empty()) return false;
        cur+=que.top().f;
        if(cur>s) return false;
        for(int k=i;k>=max(0,i-t+1);k--)
            ans[bug[k].id]=que.top().id;
        que.pop();
    }
    return true;
}
int main()
{
    scanf("%d%d%d",&n,&m,&s);
    for(int i=0;i<m;i++) scanf("%d",&bug[i].sk),bug[i].id=i;
    for(int i=0;i<n;i++) scanf("%d",&stu[i].sk);
    for(int i=0;i<n;i++) scanf("%d",&stu[i].f),stu[i].id=i;
    sort(stu,stu+n);
    sort(bug,bug+m);
    if(!check(m)) {printf("NO");return 0;}
    int lb=0,ub=m+1;
    while(ub-lb>1)
    {
        int mid=(ub+lb)/2;
        if(check(mid))
            ub=mid;
        else lb=mid;
    }
    printf("YES
");
    check(ub);
    for(int i=0;i<m;i++)
        cout<<ans[i]+1<<" ";
    return 0;
}