问题描述 今天，公司有 m 个任务要完成。第 i 个任务需要 xi 分钟才能完成。同时，该任务的难度级别为 yi。级别低于此任务级别 yi 的机器无法完成此任务。如果公司完成此任务，他们将获得 （500xi+2yi） 美元。 该公司有 n 台机器。每台机器都有一个最长工作时间和一个级别。如果任务的时间超过机器的最大工作时间，则机器无法完成此任务。每台机器只能完成一天的任务。每项任务只能由一台机器完成。 该公司希望最大限度地增加他们今天可以完成的任务数量。如果有多种解决方案，他们希望赚到最大的钱。

输入 输入包含多个测试用例。 第一行包含两个整数 N 和 M。N 是机器的数量。M 是任务数（1 < =N <= 100000,1<=M<=100000）。 以下 N 行每行包含两个整数 xi（0<xi<1440），yi（0=<yi<=100）。xi 是机器可以工作的最长时间。yi 是机器的级别。 以下 M 行各包含两个整数 xi（0<xi<1440），yi（0=<yi<=100）。xi 是我们完成任务所需的时间。yi 是任务的级别。

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

样本输入 1 2 100 3 100 2 100 1

示例输出 1 50004

思路:有两个变量:time和level;又有两个要求:任务最大,钱最多;

这么多的变量,怎么把他们统一,求出最值?

下面讲的有点啰嗦,耐心理解 也许

由于一个机器只能做一个任务,那么就不用考虑耗时太长.只要可以选,优先选time长的任务,因为一旦time大 1,钱就多500,由level引起的钱的差异,最多才200(这是为什么优先把time排前面的关键,决定性因素之一).那么只要time大的任务把满足要求的机器选了,并不会对后面的任务造成什么影响,因为后面的任务要求更低,一般用不上那么高级的机器.这就又回到一种贪心策略:要求高的先选-,这样不仅在一机多用时可以后悔(题解51-52);还可以在一机唯一用时(这道题),让排在后面选的任务(要求低)能选的范围尽可能大,虽然前面的任务机器选走了,但也尽可能让更多排在后面的任务选到机器.

然后考虑level怎么排:对于任务想要钱尽可能多,把level高的优先选.对于机器想要榨干它每一滴潜力,把能满足要求的level优先选,为了后面二分查找(要求从小到大)方便,所以level低的排前面

由于machine和task的排序规则不同,所以这里不想建两个结构体,重载两次

bool operator < (const ty& other) const
{
	if (time != other.time) return time > other.time;
    else   return level > other.level;//或者写this->level
}

所以在sort中用lambda [](){}

//[&a,b]修改a,访问b

//()函数传入的对象

//{}函数体

使用multiset是因为需要level从小到大排,而不是仅需要最大最小值,multi是因为有重复的level

AC代码:

#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

struct ty {
    int time, level;
} machine[100010], task[100010];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    while (cin >> n >> m) {//只要有输入
        for (int i = 1; i <= n; ++i) cin >> machine[i].time >> machine[i].level;
        for (int i = 1; i <= m; ++i) cin >> task[i].time >> task[i].level;

        sort(machine + 1, machine + n + 1, [](const ty &a, const ty &b) {
            if (a.time != b.time) return a.time > b.time;
            else return a.level < b.level;
        });
        sort(task + 1, task + m + 1, [](const ty &a, const ty &b) {
            if (a.time != b.time) return a.time > b.time;
            else return a.level > b.level;
        }); 

        long long res = 0;
        int count = 0;
        multiset<int> ms;

        for (int i = 1, j = 1; i <= m; ++i) {
            // 将时间足够的机器加入multiset,因为machine与task的time从大到小排,所以符合当前task要求的machine,一定更符合后面task的要求
            while (j <= n && machine[j].time >= task[i].time) {
                ms.insert(machine[j].level);
                ++j;
            }
            // 在multiset中查找等级足够的机器,第一个>=当前task.level即符合要求的
            auto it = ms.lower_bound(task[i].level);//multiset自带lower_bound,返回迭代器
            if (it != ms.end()/*end(是最后一个元素+1,代表没找到)*/) {
                ++count;
                res += 500 * task[i].time + 2 * task[i].level;
                ms.erase(it);//一机一用
            }
        }
        cout << count << " " << res << '\n;//别忘了换行
    }
}