洛谷 P10464 Task 题解

· · 题解

题目链接

挺不错的一道贪心题。首先观察数据范围，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;
}