Nowcoder 牛牛找工作

问题描述

牛牛找工作_牛客网

  • 题目描述
    为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
  • 输入描述
    每个输入包含一个测试用例。
    每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
    接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
    接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
    保证不存在两项工作的报酬相同。
  • 输出描述
    对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。

    算法

    吐槽：这题有毒，测试用例中有空行，需要将空行去掉！

    解法一：bruteforce

    时间复杂度：
    空间复杂度： 用来保存结果
    对于每个人，遍历所有工作寻找适合的工作中报酬最高的那个。

    解法一实现

    解法一：Python 超时

图片说明 

import sys
lines = sys.stdin.readlines()
lines = [line.strip().split() for line in lines if line.strip()] # 去空行
n_jobs, n_peers = map(int, lines[0])
difficulty, profit = [0] * n_jobs, [0] * n_jobs
for i in range(n_jobs):
difficulty[i], profit[i] = map(int, lines[1+i])
ability = list(map(int, lines[-1]))
def solution(n_peers, n_jobs, profit, difficulty, ability):
maxProfit = [0] * n_peers
for i in range(n_peers):
for j in range(n_jobs):
if difficulty[j] <= ability[i] and profit[j] > maxProfit[i]:
maxProfit[i] = profit[j]
for pro in maxProfit:
print(pro)
if __name__ == '__main__':
solution(n_peers, n_jobs, profit, difficulty, ability)

解法二：

如果某人的能力大于等于工作难度，称工作是适合这个人的

  1. 对报酬排序
    由于问题是求最高报酬，因此可以考虑将报酬 profit 数组进行排序，先考虑最高报酬的工作是否可以解决，如果不行，再考虑次高报酬的工作是否可以解决...
    （如果不对 profit 排序，那么当某个人找到一份合适的工作时，是需要继续向下遍历的，因为不知道之后是否会遇到报酬更高的适合的工作。因此排序后可以减少循环的次数）
  2. 对能力排序
    发现下面一个事实：如果有两个人 a、b，如果 a 的能力 <= b 的能力，那么 a 的最高报酬 <= b 的最高报酬
    因此可以对能力排序。

    复杂度分析

    N 表示工作数，M 表示人数
    时间复杂度： ，两次排序，双指针最多运行 次
    空间复杂度：

    解法二实现

    解法二python
    import sys
lines = sys.stdin.readlines()
lines = [line.strip().split() for line in lines if line.strip()] # 去空行
n_jobs, n_peers = map(int, lines[0])
difficulty, profit = [0] * n_jobs, [0] * n_jobs
for i in range(n_jobs):
difficulty[i], profit[i] = map(int, lines[1+i])
ability = list(map(int, lines[-1]))
def solution(n_peers, n_jobs, profit, difficulty):
maxProfit = [0] * n_peers
# 根据 profit 排序
profit, difficulty = zip(*sorted(zip(profit, difficulty)))
# 这里使用了索引数组，因为输出是按照原来ability的顺序输出的，因此不能对ability直接排序
ability_idx = sorted(range(n_peers), key=lambda i: ability[i])
i, j = n_peers - 1, n_jobs - 1
while i >= 0 and j>=0:
if difficulty[j] <= ability[ability_idx[i]]:
maxProfit[ability_idx[i]] = profit[j]
i -= 1
else:
j -= 1
for pro in maxProfit:
print(pro)
if __name__ == '__main__':
solution(n_peers, n_jobs, profit, difficulty)