「一本通 1.1 例 5」智力大冲浪
题解
- 带限期和罚款的单位时间任务调度
- 按期限排序
- 用优先队列维护
- 若当前时间完成的任务数少于该时间能完成的任务数,直接将权值入队
- 若已经相等,取出队列中最小的元素与当前权值比较,将较大的入队
- 最后累加队列中的元素权值,$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;
}