贪心

1 收入公式有点亮眼: 500 * x + 2 * y
其中0 < x < 1440
0 <= y <= 100
x和y都是整数.
x变动1, 收入变化500
y按照最大变动100, 收入变化才只有200.
因此, 非常容易想到, 对于任务的优先级, 应该是先基于x, 再基于y
根据上面分析得到的优先级, 对任务进行排序.

2 逆序遍历任务.
寻找满足时间要求和级别要求的机器.
如果没有这样的机器, 那么这个任务是无法完成的, 跳过.
如果有且仅有一个这样的机器, 那么就选择这个机器去完成这个任务.
如果有多个满足条件的机器, 那么选择级别最低的那个机器.
很多题解里面是这样说, 但没有解释为什么?(可能是他们觉得过于显然了)
我当时看的时候, 有一些疑惑: 为什么选择级别最低的那个机器, 而不是时间最小的那个机器?
经过了一段时间的思考, 终于搞明白了为什么.
比如其中有两个机器满足条件, 分别为(x1, y1), (x2, y2)
其中x1 < x2, y1 > y2.
先考时间这个变量, 发现时间变量根本不影响后面的选择.
因为是根据时间逆序遍历的, 任务要求的时间是越来越小的, 这两个机器无论剩下哪个, 都是满足后面任务的时间要求的.
而后面任务的级别要求没有什么规律可言, 因此, 应该尽可能剩下级别高的机器给后面的任务, 因此, 当有多个机器可供选择的时候, 优先选择级别最低的机器.

时间复杂度

O(M * log(N))

本来想使用sortedcontainers里面的SortedList, 大致上等价于C++中的multiset.
后来发现ACWing不支持这个库.
就使用了Python的list代替.
不过, 不影响时间复杂度.

Python 代码

from bisect import bisect_left, insort_left

N, M = map(int, input().split())

workers = []
tasks = []
for i in range(N):
    x, y = map(int, input().split())
    workers.append((x, y))
for i in range(M):
    x, y = map(int, input().split())
    tasks.append((x, y))

workers.sort()
tasks.sort()
#print(workers, tasks)

cnt = 0
val = 0
degrees = []
j = N - 1
for i in range(M - 1, -1, -1):
    while j >= 0 and workers[j][0] >= tasks[i][0]:
        insort_left(degrees, workers[j][1])
        j -= 1
    idx = bisect_left(degrees, tasks[i][1])
    if idx < len(degrees):
        cnt += 1
        val += 500 * tasks[i][0] + 2 * tasks[i][1]
        degrees.pop(idx)
print(cnt, val)

注意到等级的范围很小, 可以考虑使用计数法来表达degrees.
发现运行时间比第一个算法稍长.
第一个算法为2129 ms, 这个算法为2627 ms, 可能是因为这个范围还是偏大了点了.

N, M = map(int, input().split())

workers = []
tasks = []
for i in range(N):
    x, y = map(int, input().split())
    workers.append((x, y))
for i in range(M):
    x, y = map(int, input().split())
    tasks.append((x, y))

workers.sort()
tasks.sort()
#print(workers, tasks)

cnt = 0
val = 0
degrees = [0] * 101
j = N - 1
for i in range(M - 1, -1, -1):
    while j >= 0 and workers[j][0] >= tasks[i][0]:
        degrees[workers[j][1]] += 1
        j -= 1
    idx = 101
    for k in range(tasks[i][1], 101):
        if degrees[k]:
            idx = k
            degrees[k] -= 1
            break
    if idx < 101:
        cnt += 1
        val += 500 * tasks[i][0] + 2 * tasks[i][1]
print(cnt, val)