本文主要是介绍牛客网-牛牛找工作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：https://www.nowcoder.com/questionTerminal/46e837a4ea9144f5ad2021658cb54c4d
时间限制：2秒
空间限制：65536K
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下， 牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标 准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。 输入描述: 每个输入包含一个测试用例。 每个测试用例的第一行包含两个正整数，分别表示工作的数量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
超时算法:
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include<iostream>
#include<algorithm>using namespace std;struct job {int Di;//难度int Pi;//报酬
} Job[100001];int Ai;bool cmp(struct job a, struct job b) {return a.Pi > b.Pi; //报酬
}int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {for (int i = 0; i < n; i++) { //n为工作数量cin >> Job[i].Di;cin >> Job[i].Pi;}sort(Job, Job + n, cmp);for (int i = 0; i < m; i++) {//m为小伙伴数量 /*注意：这里超时了，因为10e5 * 10e5 超过2秒的时间。 1秒约10e8*/cin >> Ai;for (int j = 0; j < n; j++) {//n为工作数量if (Ai >= Job[j].Di) {cout << Job[j].Pi<<endl ;break;}}}}return 0;
}正确解法：
#include <iostream>
#include <queue>
#include <cstdio>
#include <cstring>
#include<iostream>
#include<algorithm>using namespace std;struct job { //工作int Di;//难度int Pi;//报酬
} Job[100001];struct ai { //人int i;//序号int power;//能力int money=0;//报酬
} Ai[100001];bool cmp(struct job a, struct job b) {return a.Di < b.Di; //难度
}bool cmp2(struct ai a, struct ai b) {return a.power < b.power; //能力
}bool cmp3(struct ai a, struct ai b) {return a.i < b.i; //序号
}int main() {int n, m;while (scanf("%d%d", &n, &m) != EOF) {for (int i = 0; i < n; i++) { //n为工作数量cin >> Job[i].Di;cin >> Job[i].Pi;}sort(Job, Job + n, cmp);for (int i = 0; i < m; i++) { //m为小伙伴数量Ai[i].i=i;cin >> Ai[i].power;}sort(Ai, Ai + m, cmp2);//多思考，//人的能力 10 30 45 70//工作需要的能力 12 13 14 15 37 59// 30人的能力 大于 工作的能力12 13 14 15 所以选其中最大的赋值给30能力的人int j=0;int maxMoney=0;for(int i=0;i<m;i++){while(j<n){if(Job[j].Di>Ai[i].power){ //工作的能力 大于 人的能力 ，退出break;}maxMoney=max(maxMoney,Job[j].Pi);j++;}Ai[i].money=maxMoney;}sort(Ai, Ai + m, cmp3);for(int i=0;i<m;i++){cout<<Ai[i].money<<endl;}}return 0;}
这篇关于牛客网-牛牛找工作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
