题解：P10464 Task

题目传送门

这道题我们的思路就是根据题目中所说的尽可能的完成更多的任务，而这题的突破口就是更小的

x

。所以我们便可以从小到大排序，因为这样我们便可以枚举一遍机器人的同时，再使用

dis[i]

表示在

i

的时间有多少可以的任务，因为机器人的时间是单调不递减的。维护

dis

的代码：

CPP

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

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

AC Code：

CPP

#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;
}

文章操作

题目传送门

AC Code：

相关推荐

评论

题解：P10464 Task