[编程题]牛牛找工作
- 热度指数：132799 时间限制：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
精华题解
题目难度：三星考察点：贪心、排序 方法1：暴力算法 分析：对于每个小伙伴，从1-n遍历一遍找到超过自身能力值的情况下报酬最高的那个人，输出即可。 复杂度分析：时间复杂度：O(m*n)空间复杂度：O(n) 代码：#include <bits/stdc++.h>
using namespa
展开全文
方法： 排序+双指针 想法： 工人们只能做难度小于等于他能力值的工作，将工作的难度按升序排序，遍历工作难度的同时记录最大收益，一定是当前工人能获得的最大收益。 算法： 由于不止一个工人，如果每个工人都按上述操作进行，时间复杂度是Ｏ（ｎ＊ｍ）的，不能通过此题。考虑将工人的能力值也按升序排序，不失
展开全文
1. 牛牛找工作 题目描述：为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交
展开全文
在本题中，最先想到的是，将所有的能力值及对应的薪酬放到map中，然后每个循环对比，输出每个能力值所能获得的最大值，但是这样肯定超时，O（n*m）。 将所有的能力值和薪酬一一对应填入map中，如果当前能力值有多个对应薪酬，只添加最高的那个。 将同学的能力值也一一加入map中，如果原先已经有就直接跳过
展开全文
Nowcoder 牛牛找工作 问题描述 牛牛找工作_牛客网 题目描述为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛
展开全文
问题信息
通过挑战的用户
查看代码-
2023-03-01 18:34:00 -
2023-02-22 22:45:46
-
2023-01-14 14:19:06
-
2023-01-04 00:48:44 -
2022-11-22 16:04:50
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
