题目链接

算法竞赛进阶指南-40.任务

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

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

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

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

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

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

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

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

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

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

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

输入格式

输入包含几个测试用例。

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

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

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

输出格式

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

数据范围

$1 \le N,M \le 100000$,
$0 < x_i < 1440$,
$0 \le y_i \le 100$

输入样例：

1 2
100 3
100 2
100 1

输出样例：

1 50004

Method : 贪心

确实难，是二分图的匹配问题，但是本题是完全图，可以用贪心来做, 说实话，这里的set很像

Acwing-110.防晒中的map，都是有匹配前排序(有序)，匹配后要删除(earse)的需求。

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

typedef long long LL;

struct Task{
    int time;
    int level;
};

struct Mache{
    int time;
    int level;
};

const int N = 1e5 + 7;
const int M = 1e5 + 7;

Mache mache[N];
Task task[M];

int n, m;

int main() {
    while (cin >> n >> m) {
        for (int i = 0; i < n; i ++) {
            scanf("%d %d", &mache[i].time, &mache[i].level);  
        }
        for (int i = 0; i < m; i ++) {
            scanf("%d %d", &task[i].time, &task[i].level); 
        }
        
        // 排序
        sort(mache, mache + n, [&](Mache& a, Mache& b) -> bool {
            if (a.time == b.time) return a.level < b.level;
            else return a.time < b.time;
            return a.time < b.time;
        });
        sort(task, task + m, [&](Task& a, Task& b) -> bool {
            if (a.time == b.time) return a.level < b.level;
            else return a.time < b.time;
        });
        
        int cnt = 0;
        LL res = 0;
        multiset<int> st_level; // 维护一个有序可重复的集合
                                // 为什么不直接用数组 + sort？ 因为后续还要删掉其中的一个元素
        // 以任务为主体
        for (int i = m - 1, j = n - 1; i >= 0; i --) {
            while (j >= 0 && mache[j].time >= task[i].time) {
                st_level.insert(mache[j].level);
                j --;
            }

            // 存在任务且任务可被执行
            auto it = st_level.lower_bound(task[i].level);
            if (it != st_level.end()) {
                res += 500 * task[i].time + 2 * task[i].level;
                cnt ++;
                st_level.erase(it);
            }
            
        }
        
        cout << cnt << " " << res << endl;   
    }

    return 0;
}

复杂度分析

• 时间复杂度：${O(max(n\log n, m\log n))}$， 其中前面的$n\log n$是sort的时间复杂度,后面的$m\log n$是m次$for$循环 * 里面$lower\_bound$的时间复杂度。

• 空间复杂度：${O(max(N, M)}$。