题目描述

今天某公司有M个任务需要完成。

每个任务都有相应的难度级别和完成任务所需时间。

第i个任务的难度级别为$y_i$，完成任务所需时间为$x_i$分钟。

如果公司完成此任务，他们将获得$（500 * x_i + 2 * y_i）$美元收入。

该公司有N台机器，每台机器都有最长工作时间和级别。

如果任务所需时间超过机器的最长工作时间，则机器无法完成此任务。

如果任务难度级别超过机器的级别，则机器无法完成次任务。

每台机器一天内只能完成一项任务。

每个任务只能由一台机器完成。

请为他们设计一个任务分配方案，使得该公司能够最大化他们今天可以完成的任务数量。

如果有多种解决方案，他们希望选取赚取利润最高的那种。

输入格式
输入包含几个测试用例。

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

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

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

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

数据范围
$1≤N,M≤100000$
$0<x_i<1440$
$0≤y_i≤100$

样例

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

贪心

这道题目标签是不是过高了?这道题目还是挺好贪心的,我们发现时间长的任务,就给满足条件,y[i]最小的机器就可以让利润最大,因为这道题目中,工作的时间占利润的最大比例,所以我们以时间为第一关键字,机器和任务的工作等级为第二关键字即可.

C++ 代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define fir(i,a,b) for (ll i=a;i<=b;i++)
const int N=100100;
pii e[N],f[N];
ll cnt[105],n,m,ans,num,i,j,k;
int cmp(pii a,pii b)
{
    if (a.first==b.first)
        return a.second>b.second;
    return a.first>b.first;
}
int main()
{
    ios::sync_with_stdio(false);//优化cin
    cin>>n>>m;
    fir(i,1,n)
        cin>>e[i].first>>e[i].second;
    fir(i,1,m)
        cin>>f[i].first>>f[i].second;
    sort(e+1,e+1+n,cmp);
    sort(f+1,f+1+m,cmp);
    //排序贪心
    j=1;
    fir(i,1,m)
    {
        while(j<=n && e[j].first>=f[i].first)//找满足条件的机器
        {
            cnt[e[j].second]++;//放入这个等级的空间
            j++;//下一个
        }
        fir(k,f[i].second,100)//机器的等级从满足条件的最低到最高
        {
            if(cnt[k])//如果有这个等级的机器
            {
                num++;//这个任务可以接下来
                cnt[k]--;//这个机器已经被使用了
                ans+=500*f[i].first+2*f[i].second;//计算答案
                break;//任务完成了
            }
        }
    }
    cout<<num<<" "<<ans<<endl;
    return 0;
}
//话说我居然写了这么多注释.....