自动搬运

查看原文

来自洛谷，原作者为

	MinimumSpanningTree **

搬运于2025-08-24 22:58:12，当前版本为作者最后更新于2024-04-20 12:39:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

挺不错的一道贪心题。首先观察数据范围，$x$ 最小可以是 $1$，$y$ 最大可以是 $100$，根据收益可以计算出 $1\times500=500$，$100\times2=200$，由此可见，在 $x$ 最小，$y$ 最大时，$x$ 带来的收益却比 $y$ 大。于是我们可以得出结论：无论如何，$x$ 的价值永远比 $y$ 大。这就是我们贪心的突破口，由此结论我们可以优先考虑 $x$。

于是我们将机器和任务都按 $x$ 为第一关键字，$y$ 为第二关键字从大到小排序。接下来依次枚举任务，找出所有 $x$ 能满足当前任务的机器，再从这些机器里寻找满足 $y$ 的，如果存在多个机器可以满足，则我们贪心的选取 $y$ 最小的那个。因为 $y$ 并不是有序的，后面可能会出现更大的 $y$，当然要尽量把大的留给后面的了。

对于查找满足 $x$ 的机器：这时我们会发现，如果枚举每次任务的时候用遍历的方式寻找机器，$O(nm)$ 明显是超时的。但因为机器和任务的 $x$ 都是有序的，若当前机器不能满足任务，则后面的机器也不能，若某个机器满足当前任务，则它必定也满足下一个任务。故我们可以维护一个指针，每一轮查找新的可以满足的机器。

对于查找满足 $y$ 的机器：与上面相同，直接枚举显然是超时的。但观察到 $y\le100$，容易想到我们可以使用一个数组 $c_i$ 表示 $y=i$ 的机器数量，$O(100m)$ 可以通过。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=100100,M=110;
int n,m,c[M],p,cnt;
ll ans;
struct node
{
	ll x,y;
}a[N],b[N];
bool cmp(node a1,node a2)
{
	if(a1.x!=a2.x) return a1.x>a2.x;
	return a1.y>a2.y;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld%lld",&a[i].x,&a[i].y);
	for(int i=1;i<=m;i++) scanf("%lld%lld",&b[i].x,&b[i].y);
	//从大到小排序 
	sort(a+1,a+n+1,cmp);
	sort(b+1,b+m+1,cmp);
	for(int i=1;i<=m;i++)//枚举任务 
	{
		while(p<n&&a[p+1].x>=b[i].x)//维护指针，寻找新的可以满足x的机器 
		{
			p++;
			c[a[p].y]++; 
		}
		for(int j=b[i].y;j<=100;j++)//在满足x的机器里，寻找满足y的 
		{
			if(c[j])
			{
				cnt++;
				c[j]--;//记得去掉 
				ans+=b[i].x*500+b[i].y*2;
				break;//找到第一个就退出，因为要贪心地取y最小的 
			}
		}
	}
	printf("%d %lld",cnt,ans);
	return 0;
}