文章目录[x]
- 1:题目内容
- 1.1:题目描述
- 1.2:输入描述:
- 1.3:输出描述:
- 2:示例
- 2.1:输入
- 2.2:输出
- 3:第一次：
- 4:第二次：
- 5:第三次（网上查询）：
题目
题目内容
题目描述
为了找到自己满意的工作，牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下，牛牛选择报酬最高的工作。在牛牛选定了自己的工作后，牛牛的小伙伴们来找牛牛帮忙选工作，牛牛依然使用自己的标准来帮助小伙伴们。牛牛的小伙伴太多了，于是他只好把这个任务交给了你。
输入描述:
每个输入包含一个测试用例。 每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N<=100000)和小伙伴的数量M(M<=100000)。 接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di<=1000000000)和报酬Pi(Pi<=1000000000)。 接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai<=1000000000)。 保证不存在两项工作的报酬相同。
输出描述:
对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。
示例
输入
3 3 1 100 10 1000 1000000000 1001 9 10 1000000000
输出
100 1000 1001 题目链接：https://www.nowcoder.com/practice/46e837a4ea9144f5ad2021658cb54c4d?tpId=98&tqId=32824&tPage=1&rp=1&ru=/ta/2019test&qru=/ta/2019test/question-ranking
第一次：
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
typedef struct job{
int Di;
int Pi;
}j,*pj;
int main(){
int m,n;
cin>>n>>m;
int *ability=new int[m];
vector<pj> job_info;
for(int i=0;i<n;i++){
pj node=(pj)malloc(sizeof(j));
cin>>node->Di>>node->Pi;
job_info.push_back(node);
}
for(int i=0;i<m;i++)
cin>>ability[i];
int max=0;
for(int i=0;i<m;i++){
for(int k=0;k<n;k++){
if (ability[i]>=job_info[k]->Di)
if (job_info[k]->Pi>max)
max=job_info[k]->Pi;
}
cout<<max<<endl;
max=0;
}
}
第二次：
#include <iostream>
#include <vector>
#include <stdlib.h>
using namespace std;
int main(){
unsigned int n,m;
cin>>n>>m;
unsigned int *data=new unsigned int[2*n+m];
for(int i=m;i<2*n+m;i++)
cin>>data[i];
for(int i=0;i<m;i++)
cin>>data[i];
unsigned int max=0;
for(int i=0;i<n;i++){
int Di=n,Pi=n+1;
while(Pi<=2*n+m-1){
if(data[i]>=data[Di])
if(max<data[Pi])
max=data[Pi];
Di+=2;
Pi+=2;
}
cout<<max<<endl;
max=0;
}
}
经过这两次后，我发现仅能完成40%的用例，剩下的60%因为程序结构过复杂，导致运行时间超时，未能通过。
经过网上查询后，我了解到了贪心算法的概念，下面是我查到的答案：
第三次（网上查询）：
#include <iostream>
#include <cstdio>
#include <cstring>
#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;
}
答案来自于：https://blog.csdn.net/u011630575/article/details/79874315