题目描述

输入包含几个测试用例。

对于每个测试用例，第一行包含两个整数N和M，分别代表机器数量和任务数量。

接下来N行，每行包含两个整数xi,yi，分别代表机器最长工作时间和机器级别。

再接下来M行，每行包含两个整数xi,yi，分别代表完成任务所需时间和任务难度级别。

输出格式
对于每个测试用例，输出两个整数，代表公司今天可以完成的最大任务数以及他们将获得的收入。

数据范围
1≤N,M≤100000,
0<xi<1440,
0≤yi≤100

样例

输入样例：
1 2
100 3
100 2
100 1
输出样例：
1 50004

算法1

(暴力枚举) $O(n)$

见代码吧。

时间复杂度

O(n)

参考文献

C++ 代码

//挺难的一道贪心题(起码对我来说是这样的...)
//首先这是一道二维费用的贪心,即每一个任务都有两个属性,x和y.
//但我们仔细观察题目就会发现,x每变化1,总价值变化500,而y就算变化为100,总价值才变化200
//这就说明总价值由x决定,换句话说,x大的任务,它对应的价值一定最大.
//接下来我们先思考一维的情况,即如果只有一个x,那我们就可以两个分别排序,给每一个任务找一个满足要求且x最小的机器分配.
//按照这个思路,我们对二维也这样处理,即对任务以x为第一关键字排序(因为他对总价值影响更大),按y为第二关键字排序.
//之后给每一个任务安排一个机器,使得机器满足他的条件,使得y最小.
//为什么不要求x呢,因为我们可以发现一个性质,如下:
//machine (4,2) (4,1) (3,2) (3,1) (2,5)...
//task    (4,1) (4,0) (3,2) (1,2) (1,1)...
//我们考虑第一个任务i,x值比他大的机器,也一定大于它后面的任务,所以此时我们就不用考虑
//这时这些机器的x是什么了,因为限制他们的只有y值,例如上图的任务(3,2),满足他的机器一定x一定满足它后面的任务,//所以此时为了让后面的任务有更好的决策,我们在这些机器中选择y最小的即可.
//具体怎么求,可以用两个指针i,j.分别扫任务和机器,并以此记录扫过机器的y值
//(此时他们的x值对我们没有价值,因为它的x值一定满足后面的任务),每次在y值里找最小的一个即可. 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=100010;
int n,m,cnt[N];
struct gg{int x,y;}machine[N],task[N];
inline int read()
{
    int x=0,ff=1;
    char ch=getchar();
    while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getchar();}
    while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    return x*ff;
}
inline bool cmp(gg x,gg y)
{
    if(x.x==y.x) return x.y>y.y;
    else         return x.x>y.x;
}
int main()
{
    while(cin>>n>>m)
    {
        for(int i=1;i<=n;++i) machine[i].x=read(),machine[i].y=read();
        for(int i=1;i<=m;++i) task[i].x=read(),task[i].y=read();
        memset(cnt,0,sizeof(cnt));
        sort(machine+1,machine+n+1,cmp);
        sort(task+1,task+m+1,cmp);
        int j=1,num=0;
        ll ans=0;
        for(int i=1;i<=m;++i)
        {
            for(;j<=n&&machine[j].x>=task[i].x;++j) cnt[machine[j].y]++;
            for(int k=task[i].y;k<=100;++k)
            {
                if(cnt[k])
                {
                    cnt[k]--;
                    num++;
                    ans+=task[i].x*500+task[i].y*2;
                    break;
                }
            }
        }
        printf("%d %lld\n",num,ans);
    }
    return 0;
}