[编程题]牛牛找工作
- 热度指数：4819 时间限制：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)。
保证不存在两项工作的报酬相同。
输出描述:
对于每个小伙伴，在单独的一行输出一个整数表示他能得到的最高报酬。如果他找不到工作，则输出0。一个工作可以被多个人选择。
示例1
输入
3 3 1 100 10 1000 1000000000 1001 9 10 1000000000
输出
100 1000 1001
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
TreeMap<Integer,Integer> map=new TreeMap<>();
int m=sc.nextInt();
int n=sc.nextInt();
int [][]work=new int[m][2];
for(int i=0;i<m;i++){
work[i][0]=sc.nextInt();//工作难度
work[i][1]=sc.nextInt();//钱
}
Arrays.sort(work,new Comparator<int[]>(){//按工作难度来排序
@Override
public int compare(int[] num1,int []num2){
return num1[0]-num2[0];
}
});
//dp来使相应的工作难度获利最大
//并且把结果存入map中
for(int i=1;i<m;i++){
work[i][1]=Math.max(work[i-1][1],work[i][1]);
map.put(work[i-1][0],work[i-1][1]);
}
map.put(work[m-1][0],work[m-1][1]);//最后一项加入（避免出现异常）
for(int i=0;i<n;i++){//根据难度来找工作
int dif=sc.nextInt();
Integer index=map.floorKey(dif);
if(index!=null)
System.out.println(map.get(index));
else
System.out.println(0);
}
}
}
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
TreeMap<Integer,Integer> map=new TreeMap<>();
int m=sc.nextInt();
int n=sc.nextInt();
int [][]work=new int[m][2];
for(int i=0;i<m;i++){
work[i][0]=sc.nextInt();//工作难度
work[i][1]=sc.nextInt();//钱
}
Arrays.sort(work,new Comparator<int[]>(){//按工作难度来排序
@Override
public int compare(int[] num1,int []num2){
return num1[0]-num2[0];
}
});
//dp来使相应的工作难度获利最大
//并且把结果存入map中
for(int i=1;i<m;i++){
work[i][1]=Math.max(work[i-1][1],work[i][1]);
map.put(work[i-1][0],work[i-1][1]);
}
map.put(work[m-1][0],work[m-1][1]);//最后一项加入（避免出现异常）
for(int i=0;i<n;i++){//根据难度来找工作
int dif=sc.nextInt();
Integer index=map.floorKey(dif);
if(index!=null)
System.out.println(map.get(index));
else
System.out.println(0);
}
}
}
发表于 2018-06-01 15:20:57
回复(12)
按照工作难度对工作数组排序后，遍历有序数组，更新报酬为当前难度下的最大报酬。而后，对每个伙伴只需二分搜索确定其胜任的最大工作难度即可获取当下最大报酬。
public class FindJob {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int jobNum = in.nextInt();
int friendNum = in.nextInt();
int[][] jdArray = new int[jobNum][2];
for (int x = 0; x < jobNum; x++) {
jdArray[x][0] = in.nextInt();
jdArray[x][1] = in.nextInt();
}
int[] ability = new int[friendNum];
for (int x = 0; x < friendNum; x++) {
ability[x] = in.nextInt();
}
process2(jdArray, ability);
}
public static void process2(int[][] jdArray, int[] ability) {
// 按照工作难度升序排序
Arrays.sort(jdArray, (int[] jd1, int[] jd2) -> {return jd1[0] - jd2[0];});
// 更新每个工作的报酬为当前难度所能获取的最大报酬
for (int i = 0; i < jdArray.length - 1; i++) {
if (jdArray[i][1] > jdArray[i + 1][1]) {
jdArray[i + 1][1] = jdArray[i][1];
}
}
// 二分查找确定能胜任的最大工作难度及其最大报酬
for (int i = 0; i < ability.length; i++) {
int index = Arrays.binarySearch(jdArray, new int[] {ability[i], 0}, (int[] jd1, int[] jd2) ->{
return jd1[0] - jd2[0];});
index = index < 0 ? -(index + 1) - 1: index;
System.out.println(index >= 0 ? jdArray[index][1] : 0);
}
}
}
编辑于 2018-07-10 19:40:12
回复(4)
//非原创，借鉴楼上求天求地求offer解析，将TreeMap的使用改为二分查找
import java.util.*;
public class Main{
static int n,m;
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int[][] t = new int[n][2];
for(int i=0;i<n;i++){
t[i][0] = sc.nextInt();
t[i][1] = sc.nextInt();
}
//自定义排序
Arrays.sort(t,new Comparator<int[]>(){
@Override
public int compare(int[] a,int[] b){
return a[0]-b[0];
}
});
//dp使得对应的工作难度获得最大酬劳
for(int i=1;i<n;i++){
t[i][1] = max(t[i-1][1],t[i][1]);
}
for(int i=0;i<m;i++){
int a = sc.nextInt();
int index = find(a,t);
if(index==-1)
System.out.println(0);
else
System.out.println(t[index][1]);
}
}
//二分查找
public static int find(int a,int[][] s){
int mid = (0+n)/2;
int lo=0,hi=n-1;
while(lo<=hi){
mid = (lo+hi)/2;
if(a<s[mid][0]){
hi=mid-1;
} else if(a>s[mid][0]){
lo=mid+1;
} else if(a==s[mid][0]){
return mid;
}
}
return hi;
}
public static int max(int a,int b){
if(a>b)
return a;
return b;
}
}
发表于 2019-08-01 21:10:15
回复(0)
package ForNetEasy;
//参考非全的春天，感谢
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class NiuNiuFindJobs {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int [][]job = new int[n][2];
int []partner = new int[m];
for(int i = 0;i<n;i++){
String str = sc.nextLine();
job[i][0] = sc.nextInt();
job[i][1] = sc.nextInt();
}
for(int i =0;i<m;i++){
partner[i] = sc.nextInt();
}
sc.close();
//从小到大排序
Arrays.sort(job,new Comparator<int[]>(){
public int compare(int[] a,int[] b ){
return a[0] - b[0];
}
});
//更新报酬值[1 10][2 8]为 [1 10][2 10]
for(int i =1;i<n;i++){
job[i][1]= job[i-1][1]>job[i][1]? job[i-1][1]:job[i][1];
}
//折半查找
for(int i=0;i<m;i++){
int b = 0;
int e = n-1;
int max = 0;
while(b<=e){
int mid = (b+e)/2;
if(partner[i]>=job[mid][0]) {
max = job[mid][1];
b=mid+1;
}else{
e= mid-1;
}
}
System.out.println(max);
}
}
}
//参考非全的春天，感谢
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class NiuNiuFindJobs {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int [][]job = new int[n][2];
int []partner = new int[m];
for(int i = 0;i<n;i++){
String str = sc.nextLine();
job[i][0] = sc.nextInt();
job[i][1] = sc.nextInt();
}
for(int i =0;i<m;i++){
partner[i] = sc.nextInt();
}
sc.close();
//从小到大排序
Arrays.sort(job,new Comparator<int[]>(){
public int compare(int[] a,int[] b ){
return a[0] - b[0];
}
});
//更新报酬值[1 10][2 8]为 [1 10][2 10]
for(int i =1;i<n;i++){
job[i][1]= job[i-1][1]>job[i][1]? job[i-1][1]:job[i][1];
}
//折半查找
for(int i=0;i<m;i++){
int b = 0;
int e = n-1;
int max = 0;
while(b<=e){
int mid = (b+e)/2;
if(partner[i]>=job[mid][0]) {
max = job[mid][1];
b=mid+1;
}else{
e= mid-1;
}
}
System.out.println(max);
}
}
}
发表于 2018-06-08 10:38:18
回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int n=s.nextInt();//工作数量
int m=s.nextInt();//小伙伴的数量M
int[][] work=new int[n][2];
for (int i = 0; i <n; i++) {
for (int j=0;j<2;j++){
work[i][j]=s.nextInt();
}
}//工作的难度Di和报酬Pi 放在二维数组里
//System.out.println(Arrays.deepToString(work)+"ce1");//日志检测
int[] fri=new int[m];
for (int i = 0; i < m; i++) {
fri[i]=s.nextInt();
}//M个小伙伴的能力值Ai
//System.out.println(Arrays.toString(fri)+"ce2");//日志检测
for (int i=0;i<fri.length;i++){
int temp=0;//保存可以接受的工作中 最大的报酬
for (int k=0;k<work.length;k++){
if (fri[i]>=work[k][0] && temp<work[k][1]){//如果能力值大于难度
temp=work[k][1];
}
}
System.out.println(temp);
}
}
} 我的想法是用一个临时变量来保存符合的工作中报酬最大的那一项，为什么会报运行超时呢，有什么优化的方案吗？求解答
发表于 2019-08-06 11:25:37
回复(1)
看注释。
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
int[][] work = new int[n][2];
for(int i = 0; i< n; i++) {
work[i][0] = scanner.nextInt();
work[i][1] = scanner.nextInt();
}
Arrays.sort(work, new Comparator() { // 按照第一行排序 [@Override](/profile/992988) public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
// dp 工资，使得对应工作能力对应最大工资
// map.put(work[0][0],work[0][1]); // 第一个放第一个,不变。
for(int i = 1; i< n; i++) {
work[i][1] = Math.max(work[i-1][1],work[i][1]);
}
// 使用二分查找，小于等于工作难度的最大元素。
for(int i = 0; i< m; i++) {
int skills = scanner.nextInt();
if(skills < work[0][0]) System.out.println(0); // 第一个都胜任不了。
else{
int index = binarySearchMax(work,skills);
System.out.println(work[index][1]);
}
}
}
private static int binarySearchMax(int[][] work, int skills) {
int low = 0;
int high = work.length -1;
while (low <= high) {
int mid = low + (high -low) /2;
if(work[mid][0] > skills) {
high = mid -1;
} else {
if(mid == work.length-1 || work[mid+1][0] > skills) {
return mid;
} else {
low = mid +1;
}
}
}
// 第一个元素都被它 大。
return -1;
}
}
编辑于 2019-08-03 11:34:12
回复(0)
#include<iostream>
(720)#include<algorithm>
#include<queue>
(789)#include<vector>
using namespace std;
struct Work
{
int hard;
int profit;
};
struct Ai
{
int val;
int seq;
};
class Cmp1
{
public:
bool operator()(const Work& a, const Work& b)
{
return a.hard > b.hard;
}
};
class Cmp2
{
public:
bool operator()(const Work& a, const Work& b)
{
return a.profit < b.profit;
}
};
class Cmp3
{
public:
bool operator()(const Ai& a, const Ai& b)
{
return a.val < b.val;
}
};
class Cmp4
{
public:
bool operator()(const Ai& a, const Ai& b)
{
return a.seq < b.seq;
}
};
void Get_Max_award(vector<Work>& w, vector<Ai>& v)
{
priority_queue<Work, vector<Work>, Cmp1> hq(w.begin(),w.end());
priority_queue<Work, vector<Work>, Cmp2> pq;
sort(v.begin(), v.end(),Cmp3());
for (size_t i = 0; i < v.size(); i++)
{
while (!hq.empty()&&v[i].val >= hq.top().hard)
{
pq.push(hq.top());
hq.pop();
}
v[i].val = pq.top().profit;
}
sort(v.begin(), v.end(), Cmp4());
}
int main()
{
int n, m;
while (cin >> n >> m)
{
vector<Work> w(n);
for (int i = 0; i < n; i++)
{
cin >> w[i].hard;
cin >> w[i].profit;
}
vector<Ai> v(m);
for (int i = 0; i < m; i++)
{
cin >> v[i].val;
v[i].seq = i;
}
Get_Max_award(w, v);
for (int i = 0; i < m; i++)
cout << v[i].val << endl;
}
return 0;
} 求解我这个为啥只能过60%？
发表于 2020-04-08 01:22:44
回复(3)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
private static int[][] Jobs;
private static int N, M;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();//工作
M = sc.nextInt();//人
Jobs = new int[N][2];
for (int i = 0; i < N; ++i) {
Jobs[i][0] = sc.nextInt();
Jobs[i][1] = sc.nextInt();
}
Arrays.sort(Jobs, (int[] a, int[] b) -> {
return a[0] - b[0];
});
for (int i = 1; i < N; i++) {
Jobs[i][1] = Math.max(Jobs[i][1], Jobs[i - 1][1]);
}
for (int i = 0; i < M; i++) {
int ai = sc.nextInt();
if (ai < Jobs[0][0]) {
System.out.println(0);
} else if (ai >= Jobs[N - 1][0]) {
System.out.println(Jobs[N - 1][1]);
} else {
binarySearch(ai);
}
}
}
private static void binarySearch(int ai) {
int lo = 0;
int hi = N;
//第一个大于
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (Jobs[mid][0] < ai) {
lo = mid + 1;
} else if (Jobs[mid][0] > ai) {
hi = mid;
} else {
System.out.println(Jobs[mid][1]);
return;
}
}
System.out.println(Jobs[hi - 1][1]);//最后一个不大于
}
}
编辑于 2020-02-15 21:38:15
回复(0)
| 之前自己做的测试用例没有完全过，参考了其他小伙伴的思路。 |
public class Main{
private static int binarySearchMax(int[][] work, int skills) {
int low = 0;
int high = work.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (work[mid][0] > skills) {
high = mid - 1;
} else {
if (mid == work.length - 1 || work[mid + 1][0] > skills) {
return mid;
} else {
low = mid + 1;
}
}
}
// 第一个元素都被它 大。
return -1;
}
public static void main(String[] args) {
Scanner s = new Scanner(System.in);
int N = 0;
int M = 0;
N = s.nextInt(); //工作数量
M = s.nextInt(); //小伙伴的数量
int DIPI[][] = new int[N][2];
//二维数组来存储工作难度和报酬
for (int i = 0; i < N; i++) {
DIPI[i][0] = s.nextInt();//工作难度
DIPI[i][1] = s.nextInt();
}
//对工作难度进行排序
Arrays.sort(DIPI, new Comparator<int[]>() { // 按照第一行排序 [@Override]
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
// 更新每个工作的报酬为当前难度所能获取的最大报酬
for (int i = 0; i < DIPI.length - 1; i++) {
if (DIPI[i][1] > DIPI[i + 1][1]) {
DIPI[i + 1][1] = DIPI[i][1];
}
}
//Ai 表示工作能力
int Ai[] =new int[M];
for (int j = 0; j < M; j++) {
Ai[j] = s.nextInt();
int index = binarySearchMax(DIPI, Ai[j]);
if(index==-1)
System.out.println(0);
else {
System.out.println(DIPI[index][1]);
}
}
}
}
发表于 2019-08-07 09:50:00
回复(0)
package com.jerehao.playground;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class No1 {
private static int n;
private static int m;
private static int[][] works;
private static int[][] workers;
public static void main(String[] args){
int loop = 1;
System.setIn(No1.class.getResourceAsStream("1.txt"));
Scanner scanner = new Scanner(System.in);
//loop = scanner.nextInt();
for (int i = 0; i < loop; ++i) {
n = scanner.nextInt();
m = scanner.nextInt();
works = new int[n][2]; // 0 难度，1 报酬
workers = new int[m][2]; // 0 难度，1 最大报酬
for (int j = 0; j < n; j++) {
works[j][0] = scanner.nextInt();
works[j][1] = scanner.nextInt();
}
for (int j = 0; j < m; j++) {
workers[j][0] = scanner.nextInt();
}
solve();
output();
}
scanner.close();
}
private static void solve() {
Arrays.sort(works, Comparator.comparingInt(a -> a[0]));
int max = works[0][1];
for (int i = 1; i < n; i++) {
if(works[i][1] < max)
works[i][1] = max;
else
max = works[i][1];
}
for (int i = 0; i < m; i++) {
int p = 0, q = n - 1;
while (p <= q) {
int mid = (p + q) / 2;
if(works[mid][0] < workers[i][0])
p = mid + 1;
else if(works[mid][0] > workers[i][0])
q = mid - 1;
else {
q = mid;
break;
}
}
workers[i][1] = q < 0 ? 0 :works[q][1];
}
}
private static void output() {
for (int i = 0; i < m; i++) {
System.out.println(workers[i][1]);
}
}
}
发表于 2018-07-04 20:30:58
回复(1)
import java.util.*;
public class Main { public static void main(String[] args) {
// 每个输入包含一个测试用例。
HashMap, Integer> work = new HashMap, Integer>();
ArrayList Dis = new ArrayList();
ArrayList ableList = new ArrayList();
Scanner sc = new Scanner(System.in);
// 每个测试用例的第一行包含两个正整数，分别表示工作的数量N(N和小伙伴的数量M(M。 String num = sc.nextLine(); //工作的数量 if (num == null || num == "") { return; }
String N = toArr(num)[0];
//小伙伴的数量
String M = toArr(num)[1];
// 接下来的N行每行包含两个正整数，分别表示该项工作的难度Di(Di和报酬Pi(Pi。
for (Integer i = 0; i parseInt(N); i++) {
String s = sc.nextLine(); if (num == null || num == "") {
continue;
}
String[] work_info = toArr(s);
if (work_info.length == 2) {
work.put(Integer.parseInt(work_info[0]), Integer.parseInt(work_info[1])); }
}
// 接下来的一行包含M个正整数，分别表示M个小伙伴的能力值Ai(Ai。
String s = sc.nextLine();
String[] able_info = toArr(s);
for (int i = 0; i length; i++) {
ableList.add(Integer.parseInt(able_info[i]));
}
// 对于每个小伙伴，在单独的一行输出一个正整数表示他能得到的最高报酬。一个工作可以被多个人选择。 for (int i = 0; i parseInt(M); i++) {
Integer Ai = ableList.get(i);
Set work_set = work.keySet();
Iterator iterator = work_set.iterator();
while (iterator.hasNext()) {
Dis.add(iterator.next());
}
Integer salaryMax = 0;
for (int i1 = 0; i1 ; i1++) {
if (Ai >= Dis.get(i1) && work.get(Dis.get(i1)) > salaryMax) {
salaryMax = work.get(Dis.get(i1));
}
}
System.out.println(salaryMax); } // 保证不存在两项工作的报酬相同。 } public static String[] toArr(String str) {
String[] split = str.trim().split(" "); return split; }
}
编辑于 2018-07-04 19:26:30
回复(0)
整个题目结构非常简单，就是求 小于等于能力范围内的最高奖赏。
public class FindJob {
static class Job implements Comparable<Job> {
int di;
int pi;
public Job(int di, int pi){
this.di = di;
this.pi = pi;
}
@Override
public int compareTo(Job o) { //根据难度来排序
return this.di - o.di;
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
Job[] jobs = new Job[N];
int[] ai = new int[M];
for(int i = 0; i < N; i++){
jobs[i] = new Job(scanner.nextInt(), scanner.nextInt());
}
for(int i = 0; i < M; i++){
ai[i] = scanner.nextInt();
}
Arrays.sort(jobs); //根据难度来排序
// 通过排序后，如果难度小的报酬大于难度大的报酬，那么
// 给难度大的重新赋值新的报酬，这是为了在查找下面更好计算
for(int i = 1; i < jobs.length; i++){
if(jobs[i].pi < jobs[i-1].pi)
jobs[i].pi = jobs[i-1].pi;
}
// 遍历每一个人，根据它的能力去找相应的报酬
for(int i = 0; i < M; i++){
// 通过二分查找得到小于等于能力的难度的工作
int x = findLastEqualSmaller(jobs, ai[i]);
/*
如果没有上面那个报酬替换的过程，就需要再进行遍历一次，这样ac不过
int max = 0;
for(int j = 0; j <= x; j++){
max = Math.max(max, jobs[j].pi);
}
*/
if(x == -1){
//当不存在的时候，说明没有工作合适，返回0
System.out.println(0);
}else{
System.out.println(jobs[x].pi);
}
}
}
// 小于等于key的索引，如果没有，那么返回-1
static int findLastEqualSmaller(Job[] array, int key) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid].di > key) {
right = mid - 1;
}else {
left = mid + 1;
}
}
return right;
}
}
发表于 2018-07-01 10:51:52
回复(0)
问题信息
通过挑战的用户
-
2023-03-13 20:13:46
-
2023-02-15 09:57:50
-
2022-12-27 17:47:15 -
2022-11-25 10:30:41
-
2022-10-31 18:58:33
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
