题目描述

Today the company has m tasks to complete. The ith task need xi minutes to complete. Meanwhile, this task has a difficulty level yi. The machine whose level below this task’s level yi cannot complete this task. If the company completes this task, they will get (500xi+2yi) dollars.

The company has n machines. Each machine has a maximum working time and a level. If the time for the task is more than the maximum working time of the machine, the machine can not complete this task. Each machine can only complete a task one day. Each task can only be completed by one machine.

The company hopes to maximize the number of the tasks which they can complete today. If there are multiple solutions, they hopes to make the money maximum.

输入格式

The input contains several test cases.

The first line contains two integers N and M. N is the number of the machines.M is the number of tasks(1 < =N <= 100000,1<=M<=100000).

The following N lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the maximum time the machine can work.yi is the level of the machine.

The following M lines each contains two integers xi(0<xi<1440),yi(0=<yi<=100).xi is the time we need to complete the task.yi is the level of the task.

输出格式

For each test case, output two integers, the maximum number of the tasks which the company can complete today and the money they will get.

整体思路

从题目要求可知，最终钱数是 (500xi+2yi)，所以我们应该让xi大的任务优先执行；对于xi相同的任务，应让yi大的优先执行。
因此可对任务按照xi降序排列，xi相同的按照yi降序排列；排在前面的任务优先执行。之后对机器按照相同标准重新排序，这样位置越在前面的机器可执行任务的最大时间就越大，盈利就越多。这一步操作消除了用任务选机器时，对机器时间的限制，只需要考虑其等级是否合适即可。
对于每一个任务，找到所有时间可执行该任务的机器，然后从中选出等级合适且与该任务相距最近的机器作为执行机器。

#include<stdio.h>
#include<algorithm> 
using namespace std;

struct node
{
    int time,level;

}machine[100010],task[100010];

//将机器和任务按先时间，后等级的方式逆序排列 
bool cmp(node a,node b)
{
    if(a.time!=b.time)
        return a.time>b.time;
    return a.level>b.level;
}

int main()
{
    //m台机器，n项任务 
    int m,n;
    while(scanf("%d%d",&m,&n)!=EOF)
    {
        for(int i=0;i<m;i++)
        {
            scanf("%d%d",&machine[i].time,&machine[i].level);
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d%d",&task[i].time,&task[i].level);
        }
        //对机器和任务分别进行排序 
        sort(machine,machine+m,cmp);
        sort(task,task+n,cmp);
        long long ans=0,num=0;
        int c[105]={0};
        int i=0,j=0;
        for(i=0;i<n;i++)
        {
            //对可以执行i任务的机器等级进行桶排序 
            while(j<m&&machine[j].time>=task[i].time)
            {
                c[machine[j].level]+=1;// 
                j++;
            }
            //将第i个任务难度等级作为桶排序的遍历起点 
            for(int k=task[i].level;k<=100;k++)
            {
                //找到第一个，即任务等级最小满足的机器 
                if(c[k]!=0)
                {
                    c[k]--;
                    num++;
                    ans+=500*task[i].time+2*task[i].level;
                    break;
                }
            }     
        }
        printf("%lld %lld\n",num,ans); 
    }
    return 0;
}