「一本通 1.1 例 5」智力大冲浪 | FFY's Blog

题解

• 带限期和罚款的单位时间任务调度
  • 按期限排序
    • 用优先队列维护
    • 若当前时间完成的任务数少于该时间能完成的任务数,直接将权值入队
    • 若已经相等,取出队列中最小的元素与当前权值比较,将较大的入队
    • 最后累加队列中的元素权值,$v$减去这个和即为答案

Coding:

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e3+10;
int n,l,v,ans;
struct fy
{
    int x,y;
    bool operator<(const fy&a)
    const{return x<a.x;};
}q[maxn];
struct ffy
{
    int x;
    bool operator<(const ffy&a)
    const{return x>a.x;}
};
priority_queue<ffy>qq;
int main()
{
    scanf("%d%d",&v,&n);
    for(int i=1;i<=n;i++)scanf("%d",&q[i].x);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&q[i].y);
        ans+=q[i].y;
    }
    sort(q+1,q+1+n);
    for(int i=1;i<=n;i++)
    {
        int a=q[i].x;
        int b=q[i].y;
        if(l<a)
        {
            qq.push((ffy){b});
            l++;
        }
        else 
        {
            int c=qq.top().x;
            if(b>c)
            {
                qq.pop();
                qq.push((ffy){b});
            }
        }
    }
    while(!qq.empty())
    {
        ans-=qq.top().x;
        qq.pop();
    }
    printf("%d\n",v-ans);
    return 0;
}