题解：P10464 Task

__DAN__ · 2024-12-15 13:16:23 · 题解

题目传送门

这道题我们的思路就是根据题目中所说的尽可能的完成更多的任务，而这题的突破口就是更小的 x 。所以我们便可以从小到大排序，因为这样我们便可以枚举一遍机器人的同时，再使用 dis[i] 表示在 i 的时间有多少可以的任务，因为机器人的时间是单调不递减的。维护 dis 的代码：

while(num<=m&&b[num].y<=a[i].y) nm[b[num].x].push(b[num].y),dis[b[num++].x]++;

又因为存任务的数组也是单调不递减的，所以我们完全可以使用栈来存任务的等级

AC Code：

#include<bits/stdc++.h>
using namespace std;
long long n,m,dis[1505],ans=0,cnt=0,num=1;
struct node{
    long long x,y;
}a[100005],b[100005];
bool Cmp(node x,node y){//从小到大排序
    return x.y<y.y;
}
stack<long long> nm[1505];
int main(){
    cin>>n>>m;
    for(long long i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    for(long long i=1;i<=m;i++){
        cin>>b[i].x>>b[i].y;
    }
    sort(a+1,a+n+1,Cmp);
    sort(b+1,b+m+1,Cmp);
    for(long long i=1;i<=n;i++){
        while(num<=m&&b[num].y<=a[i].y) nm[b[num].x].push(b[num].y),dis[b[num++].x]++;//维护dis数组
        for(long long j=a[i].x;j>=1;j--){
            if(dis[j]!=0){
                ans++;
                cnt+=(500*j+2*nm[j].top());//记录答案
                nm[j].pop();
                dis[j]--;
                break;
            }
        }
    }
    cout<<ans<<" "<<cnt;//<<" "<<num<<" "<<dis[1]<<" "<<dis[100];
    return 0;
}