首页 > 试题广场 >

牛牛找工作

[编程题]牛牛找工作
  • 热度指数：132760 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。

输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。
接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。
接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。
保证不存在两项工作的报酬相同。


输出描述:
对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。
示例1

输入

3 3
1 100
10 1000
1000000000 1001
9 10 1000000000

输出

100
1000
1001
算法知识视频讲解
开通博客
头像 牛客题解官
发表于 2020-06-04 11:03:22
精华题解 题目难度：三星考察点：贪心、排序 方法1：暴力算法 分析：对于每个小伙伴，从1-n遍历一遍找到超过自身能力值的情况下报酬最高的那个人，输出即可。 复杂度分析：时间复杂度：O(m*n)空间复杂度：O(n) 代码：#include <bits/stdc++.h> using namespa 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 林佳潇
发表于 2020-03-23 16:56:50
方法：　　排序+双指针 想法：　　工人们只能做难度小于等于他能力值的工作，将工作的难度按升序排序，遍历工作难度的同时记录最大收益，一定是当前工人能获得的最大收益。 算法：　　由于不止一个工人，如果每个工人都按上述操作进行，时间复杂度是Ｏ（ｎ＊ｍ）的，不能通过此题。考虑将工人的能力值也按升序排序，不失 展开全文
去ta的博客 赞 (5) 回复(0) 收起
头像 laglangyue
发表于 2020-05-13 20:30:55
1. 牛牛找工作 题目描述：为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 来来，offer来来
发表于 2020-03-20 19:53:40
在本题中，最先想到的是，将所有的能力值及对应的薪酬放到map中，然后每个循环对比，输出每个能力值所能获得的最大值，但是这样肯定超时，O（n*m）。 将所有的能力值和薪酬一一对应填入map中，如果当前能力值有多个对应薪酬，只添加最高的那个。 将同学的能力值也一一加入map中，如果原先已经有就直接跳过 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 edward01
发表于 2020-03-03 12:34:01
Nowcoder 牛牛找工作 问题描述 牛牛找工作_牛客网 题目描述为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 火星种田佬
发表于 2024-03-17 00:04:25
1.首先把所有的工作存储起来.2.我们得思考一下既然是所谓的找赚钱赚多而且能力比难度大的,不免需要排序.无非就是两个排序思路:难度排序,报酬排序 2.1难度排序,此刻然后找到一定比自己能力小的工作了,但是依然需要找难度小中钱最多的 2.2报酬排序,排序好报酬,找哪个工作难度是比我能力小的 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 排序 贪心 模拟 网易 2019 Java工程师
来自：网易2019实习生招聘...
上传者：小小
难度：
203条回答 61886浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号