首页 > 试题广场 > 牛牛找工作
[编程题]牛牛找工作
  • 热度指数:129063 时间限制: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
/*
240ms...
这道题是卡时间的,如果直接暴力枚举,复杂度O(mn),
必然会超时,卡80%,所以我们要想一个更优化的策略。
思路:
先将工作按难度排序,复杂度为O(nlogn)。
因为工作可以重复选,那么可知员工就是要选的工作
就是在他能力值范围内的最大报酬的工作,所以把每
个工作的报酬更新为其难度范围内的工作报酬的最大
值。好比如果job[i].diff<maxDiff{job[0]~job[i-1]},
那么job[i].diff=maxDiff{job[0]~job[i-1]}。

然后再对员工的能力值进行排序,复杂度为O(mlogm)。
如果员工p的能力大于等于当前工作j的难度,那么就换下一
个难度更高的工作(++j),如果员工p的能力小于当前工作的
难度,那么员工p只能胜任前一个工作(j-1),然后换下一个
能力比员工p更强的员工p+1来挑选工作。因为p+1能力比p高,
所以他就可以从工作j挑起,那么挑选工作的复杂度实际是O(m+n)。

员工挑选完工作后,把员工报酬按原序输出即可。

所以总的复杂度就是max{O(nlogn), O(mlogm), O(m+n)} < O(mn)

详情参见代码~
*/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    while(cin >> n >> m) {
        vector<pair<int, int> > job(n + 1), guy(m);
        vector<int> map(m);
        int mx = 0, index = 0, left = 0;
        job[0] = make_pair(0, 0);
        for(int i = 1; i <= n; ++ i) {
            cin >> job[i].first >> job[i].second;
        }
        for(int i = 0; i < m; ++ i) {
            cin >> guy[i].first;
            guy[i].second = i;
        }
        sort(job.begin(), job.end(), [&](pair<int, int> a, pair<int, int> b){return a.first < b.first;});
        sort(guy.begin(), guy.end(), [&](pair<int, int> a, pair<int, int> b){return a.first < b.first;});
        for(int i = 0; i <= n; ++ i) {
            mx = max(mx, job[i].second);
            job[i].second = mx;
        }
        while(left < m && index < n + 1) {
            if(guy[left].first >= job[index].first) ++ index;
            else {
                map[guy[left].second] = job[index - 1].second;
                ++ left;
            }
        }
        for(int i = left; i < m; ++ i) {
            map[guy[i].second] = job[n].second;
        }
        for(int i = 0; i < m; ++ i) {
            cout << map[i] << endl;
        }
    }
}

编辑于 2018-03-29 14:12:16 回复(21)

思路

找到难度不大于能力的所有工作里,报酬最多的。核心是用HashMap来记录难度和不超过该难度的最大报酬。
先把工作的难度和报酬映射到HashMap
把人的能力也全部读进来,放到HashMap,报酬可以先设为0.
最后按难度从小到大(所以需要先排序)更新HashMap,key为难度,value为不超过难度的最大报酬。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int t1=0,t2=0;
        HashMap<Integer,Integer> hs = new HashMap<>();
        int[] a = new int[n+m];
        int[] b = new int[m];
        for(int i=0;i<n;i++){
            t1 = sc.nextInt();
            t2 = sc.nextInt();
            a[i] = t1;
            hs.put(t1,t2);
        }
        for(int i=0;i<m;i++){
            t1 = sc.nextInt();
            a[n+i] = t1;
            b[i] = t1;
            if(!hs.containsKey(t1))
               hs.put(t1,0);
        }
        Arrays.sort(a);
        int max = 0;
        for(int i=0;i<m+n;i++){
            max = Math.max(max,hs.get(a[i]));
            hs.put(a[i],max);
        }
        for(int i=0;i<m;i++){
            System.out.println(hs.get(b[i]));
        }
    }
}
编辑于 2018-03-31 10:21:14 回复(30)

思路: 更新難度值對應的報酬為所有小於等於其難度的報酬中報酬最大的值

  • 數組按難度值從小到大排序 O(N*logN)

  • 更新每個難度對應的報酬 O(N)

  • 使用TreeMap存儲(難度,報酬)對

  • 對每一個小夥伴的ability, 取出小於或等於其ability中難度最大的key,按照key取出報酬(注意 key 可能爲空)

    總的時間複雜度: O(N*logN)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        int[][] arr = new int[N][2];
        TreeMap map = new TreeMap();
        for(int i = 0; i < N; i++) {
            arr[i][0] = sc.nextInt();
            arr[i][1] = sc.nextInt();
        }
        Arrays.sort(arr, (e1, e2) -> (int)(e1[0] - e2[0]));
        for(int i = 1; i < arr.length; i++) {
            arr[i][1] = Math.max(arr[i-1][1], arr[i][1]);
        }
        for(int i = 0; i < arr.length; i++) {
            map.put(arr[i][0], arr[i][1]);
        }
        for(int i = 0; i < M; i++) {
            int ability = sc.nextInt();
            Integer index = map.floorKey(ability);
            if(index != null) {
                System.out.println(map.get(index));
            } else {
                System.out.println(0);
            }
        }
    }
}
编辑于 2018-03-28 00:41:26 回复(22)
最短代码来了~
将职位的能力和薪水放入map中,key为能力,value为薪水,在map中就会根据key自动排序了~
结合make_pair把找工作的人也加入到map中,这样就可以一起排序了。
在map中遍历(按能力排序好了),将map->second(value)值的含义改为map->first(能力)值以内最多有多少薪水,然后按每个小伙伴的能力直接输出就好啦。
#include<iostream>
#include<map>
using namespace std;
int n,m;
map<int,int> Map;
int main(){
    cin>>n>>m;
    int a,b;
    for(int i=0;i<n;i++){
        cin>>a>>b;
        Map[a]=b;
    }
    int ai[m];
    for(int i=0;i<m;i++){
        cin>>ai[i];
        Map.insert(make_pair(ai[i], 0));//有ai[i]就插入,不然就不插入
    }
    int nowmax=0;
    for(map<int,int>::iterator it=Map.begin();it!=Map.end();it++){
        if(it->second<nowmax)it->second=nowmax;
        else if(it->second>nowmax)nowmax=it->second;
    }
    for(int i=0;i<m;i++)cout<<Map[ai[i]]<<endl;
    return 0;
}


编辑于 2020-03-07 22:23:18 回复(1)
使用map将工作需要的能力和给的报酬一一对应,map中会对key值自动排序
将人的能力也插入到这张map中,
遍历map,使得能力值对应的报酬最大化
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;

int main() {
    int N, M;//工作数量和人数
    cin >> N >> M;
    vector<int> need(N), price(N);
    for (int i = 0; i < N; i++) {
        cin >> need[i] >> price[i];
    }
    map<int, int> mp;
    for (int i = 0; i < N; i++) {
        if (mp[need[i]] < price[i]) {
            mp[need[i]] = price[i];//使mp[need[i]] 最大
        }
        //mp.insert(make_pair(need[i], price[i]));
    }
    vector<int> abilitys(M);
    for (int i = 0; i < M; i++) {
        cin >> abilitys[i];
        mp.insert(make_pair(abilitys[i], 0));//如果存在mp[abilitys[i])],返回false,如果不存在,就新建一个abilitys[i],0
    }
    
    auto pre =  mp.begin();
    auto temp = mp.begin();
    temp++;
    for (; temp != mp.end(); temp++,pre++) {//遍历mp,使得每个能力对应的报酬是最大的
        if (temp->second < pre->second)
            temp->second = pre->second;
    }
    for (int i = 0; i < M; i++) {
        cout << mp[abilitys[i]] << endl;
    }
    //for (auto it = mp.begin(); it != mp.end(); it++) {
    //    cout << it->first << " " << it->second << endl;
    //}
    //cout << mp[10] << endl;
    //system("pause");
    return 0;
}
发表于 2018-03-28 16:32:24 回复(2)
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner( System.in );
            //用TreeMap按能力值自动排号序   
        TreeMap<Integer,Integer> map = new TreeMap<>(  );
        while(cin.hasNext())
        {
            map.clear();
            int n = cin.nextInt();
            int m = cin.nextInt();
            for(int i=0;i<n;i++)
            {
                int d = cin.nextInt();
                int p = cin.nextInt();
                map.put( d,p );
            }
                 //定义一个最小值
            int Max = 0x80000000;
                 //遍历
            Iterator it = map.keySet().iterator();
            while (it.hasNext()) {
               Integer key = (Integer) it.next();
               Integer value = map.get(key);
                       //如果大于最小值,就存下来
               if(value>=Max) Max = value;
                       //如果小于 直接替换即可
               else map.put(key,Max );
            }
        for(int i=0;i<m;i++)
            {
                int a = cin.nextInt();
                        //找到小于或等于key(a)的最大键  如果不存在就赋值为null
                Map.Entry<Integer, Integer> result = map.floorEntry(a);
                if(result==null) System.out.println(0);
                else System.out.println( result.getValue() );
            }
        }
    }
}


发表于 2019-07-09 14:28:06 回复(4)

都没Python AC代码 在这里添加一个 思想还是借鉴最高票 用maps[key]表示能力值为key所能取得的最高报酬 代码如下:

import sys
def main():
    lines = sys.stdin.readlines()
    lines = [l.strip().split() for l in lines if l.strip()]
    n, m = int(lines[0][0]), int(lines[0][1])
    res = [0] * (n + m)
    abilities = list(map(int, lines[-1]))
    maps = dict()
    for index, l in enumerate(lines[1:-1]):
        d, s = int(l[0]), int(l[1])
        maps[d] = s
        res[index] = d
    for index, ability in enumerate(abilities):
        res[index + n] = ability
        if ability not in maps:
            maps[ability] = 0
    res.sort()
    maxSalary = 0
    for index in range(n + m):
        maxSalary = max(maxSalary, maps[res[index]])
        maps[res[index]] = maxSalary
    for index in range(m):
        print(maps[abilities[index]])
if __name__ == '__main__':
    main()
编辑于 2019-06-02 16:07:40 回复(2)

#include <iostream> #include <string> #include <vector> #include <algorithm> struct Work{     int d;//工作难度     int p;//工作报酬 }; struct Person{     int a;//能力值     int p;//报酬     int index;//表示小伙伴的序号 }; using namespace std; bool cmp1(Work a,Work b){     return a.d < b.d; } bool cmp2(Person a,Person b){     return a.a < b.a; } bool cmp3(Person a,Person b){     return a.index < b.index; }
int main(){     int n;//工作的数量     int m;//小伙伴的数量     cin >> n >>m;     Work* work = new Work[n];     for(int i = 0;i < n;i++){         cin >> work[i].d >> work[i].p;     }     Person* person = new Person[m];     for(int i = 0;i < m;i++){         cin >> person[i].a;         person[i].index = i;     }     sort(work,work+n,cmp1);     sort(person,person+m,cmp2);     int j = 0;     int max_money = 0;     for(int i = 0;i < m;i++){         for(;j < n;j++){             if(person[i].a < work[j].d)                 break;             max_money = max(max_money,work[j].p);         }         person[i].p = max_money;     }     sort(person,person+m,cmp3);     for(int i = 0;i < m;i++){         cout << person[i].p << endl;     }     delete[] work;     delete[] person;     return 0; }

发表于 2019-07-24 20:01:26 回复(2)
    import sys
    import bisect
    task = {}
    lines = sys.stdin.readlines()
    n, m = map(int, lines[0].strip().split()) // 由于有空行,这句可以不写
    for line in lines[1:-1]:
        if not line.strip().split(): //存在空行,你能信...
            continue
        a, b = map(int, line.strip().split())
        task[a] = max(task.get(a, 0), b)
    arr = sorted(task.keys())
    for i in range(1, len(arr)):
        if task[arr[i]] < task[arr[i -1]]:
            task[arr[i]] = task[arr[i -1]]
    skills = map(int, lines[-1].strip().split())
    for skill in skills:
        if skill in task:
            print(task[skill])
        else:
            ind = bisect.bisect(arr, skill)
            if ind == 0:
                print(0)
            else:
                print(task[arr[ind -1]])
发表于 2018-03-28 10:56:34 回复(7)

本套8道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
#include <algorithm>
using namespace std;
struct Work { int d, p; };
struct People{ int a, index, money; };
bool cmp1(Work a, Work b) {
    return a.d < b.d;
}
bool cmp2(People a, People b) {
    return a.a < b.a;
}
bool cmp3(People a, People b) {
    return a.index < b.index;
}
int main()
{
    int n, m; cin >> n >> m;
    Work *work = new Work[n];
    for (int i = 0; i < n; i++) {
        cin >> work[i].d >> work[i].p;
    }
    People *people = new People[m];
    for (int i = 0; i < m; i++) {
        cin >> people[i].a;
        people[i].index = i;
    }
    sort(work, work + n, cmp1);
    sort(people, people + m, cmp2);
    int j = 0, maxMoney = 0;
    for (int i = 0; i < m; i++) {
        while (j < n) {
            if (work[j].d > people[i].a) {
                break;
            }
            maxMoney = max(maxMoney, work[j].p);
            j++;
        }
        people[i].money = maxMoney;
    }
    sort(people, people + m, cmp3);
    for (int i = 0; i < m; i++) {
        cout << people[i].money << endl;
    }
    delete[] work;
    delete[] people;
    return 0;
}
编辑于 2018-03-28 22:06:41 回复(3)
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input=new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        //存放能力值
        int[] ability = new int[m];
        //利用TreeMap,因为它里面的数据是默认按照key升序排列,方便比较
        Map<Integer,Integer> map = new TreeMap<Integer,Integer>();
        //存入难度和薪酬
        for(int i = 0; i < n; i++){
            int hard = input.nextInt();
            int money = input.nextInt();
            map.put(hard,money);
        }
        //存入小伙伴的能力
        for(int i=0;i<m;i++){//
            int t = input.nextInt();
            ability[i]=t;
            //不在工作难度边界处的,放入map,且对应薪酬为0
            //若能力和工作难度相等,则不存,因为已经有了这组数据,下次比较的时候可以直接用
            if(!map.containsKey(t)){
                map.put(t,0);
            }
        }
        //Map.Entry用户遍历map的key和value值
        int max = Integer.MIN_VALUE;
        for(Map.Entry<Integer,Integer> entry:map.entrySet()){
            //map的值如下:
            //  key  value
            //  1    100
            //  9    0
            //  10   1000
            //  10000000000 1001
            max = Math.max(max, entry.getValue());
            //更新之后:
            //  key  value
            //  1    100
            //  9    100
            //  10   1000
            //  10000000000 1001
            map.put(entry.getKey(), max);//更新不在工作难度边界处的薪酬
        }
        for(int i = 0; i < m; i++){
             System.out.println(map.get(ability[i]));
        }
    }
}

发表于 2019-09-02 10:36:42 回复(0)
这题测试用例是真的有毒,,,有空行也不说
发表于 2018-03-28 10:46:38 回复(11)
先吐槽牛客网的编辑器,怎么粘贴格式都不对


编辑于 2018-03-30 11:04:37 回复(5)
解题思路:
  1. 自定义一个类Work来描述工作
  2. 所有的Work存入works数组中,根据工作的难度对works从小到大排序
  3. 定义一个dp数组,dp[i]表示难度小于等于works[i]的最大报酬。
  4. 对于输入的能力值,使用二分查找,扫描works数组,找到works数组中小于等于指定能力值,且下标最大的Work。记该Work的下标为index
  5. dp[index]就是结果
import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;
class Work {
	int difficulty;
	int reward;

	public Work(int difficulty, int reward) {
		super();
		this.difficulty = difficulty;
		this.reward = reward;
	}

}

public class Main {

    public static void main(String[] args) {
		findwork();
	}

	public static void findwork() {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();// 工作数量
		int m = in.nextInt();// 人数

		Work[] works = new Work[n];// 存储n份工作
		int[] dp = new int[n];// dp[n]:难度小于等于works[n].difficulty的工作的最高报酬
		// 读入n份工作
		for (int i = 0; i < n; i++) {
			int difficulty = in.nextInt();
			int reward = in.nextInt();
			Work work = new Work(difficulty, reward);
			works[i] = work;
		}
		// 根据工作的难度,对n份工作从小到大排序
		Arrays.sort(works, new Comparator<Work>() {

			@Override
			public int compare(Work o1, Work o2) {
				return o1.difficulty - o2.difficulty;
			}
		});
		// dp[i]:记录难度小于等于works[i].difficulty的最大报酬
		dp[0] = works[0].reward;
		for (int i = 1; i < works.length; i++) {
			dp[i] = dp[i - 1] > works[i].reward ? dp[i - 1] : works[i].reward;
		}

		for (int i = 0; i < m; i++) {
			int capability = in.nextInt();
			// 能力值小于所有的工作的难度
			if (capability < works[0].difficulty) {
				System.out.println(0);
				continue;
			}
			// 能力值大于等于所有的工作的难度
			if (capability >= works[n - 1].difficulty) {
				System.out.println(dp[n - 1]);
				continue;
			}
			// 二分查找,找到第一个小于capability的work
			int low = 0;
			int high = n - 1;
			while (low <= high) {
				int middle = (low + high) / 2;

				// works[middle]是符合能力值,且难度最大的工作
				if (works[middle].difficulty <= capability && works[middle + 1].difficulty > capability) {
					System.out.println(dp[middle]);
					break;
				}
				// 找到难度等于能力值,且下标最大的工作
				if (works[middle].difficulty == capability) {
					// 找到最后一个符合capability的工作
					int index = middle;
					while (index + 1 < n && works[index + 1].difficulty == capability) {
						index++;
					}
					System.out.println(dp[middle]);
					break;
				} else if (capability > works[middle].difficulty) {
					low = middle + 1;
				} else if (capability < works[middle].difficulty) {
					high = middle - 1;
				}
			}
		}
	}  
}


发表于 2020-02-20 18:08:00 回复(0)
// 懒得用Map,自己定义一个Node,存放工作的难度,工资,以及小于等于当前难度的所有工作中
// 最高的工资。用二分查找找到最接近且小于等于能力值的下标。
// 这个题输入有问题,所以BufferReader用不了会卡90%的数组越界,Scanner又非常慢
// 想要快速读入的同学可以使用StreamTokenizer
// 不过真实校招下,输入一般不会有问题;也基本不会因为Scanner超时
import java.util.*; import java.io.*;

public class Main{
    static class Node{
        int key;
        int value;
        int maxPay;
        Node(int key, int value){
            this.key = key;
            this.maxPay = this.value = value;
        }
    }
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt();
        Node[] nodes = new Node[n];
        for(int i = 0; i < n; i++){
            nodes[i] = new Node(sc.nextInt(), sc.nextInt());
        }
        Arrays.sort(nodes, (Node n1, Node n2)->n1.key - n2.key);
        for(int i = 1; i < n; i++){
            if(nodes[i].maxPay < nodes[i-1].maxPay)
                nodes[i].maxPay = nodes[i-1].maxPay;
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < m; i++){
            int index = binarySearch(nodes, sc.nextInt());
            if(index < 0) sb.append(0);
            else sb.append(nodes[index].maxPay);
            sb.append("\n");
        }
        System.out.print(sb.toString());
        sc.close();
        //br.close();
    }
    private static int binarySearch(Node[] nodes, int key){
        int from = 0; int to = nodes.length-1;
        int mid = 0;
        while(from <= to){
            mid = (from + to)>>1;
            if(nodes[mid].key == key) return mid;
            else if(nodes[mid].key < key) from = mid+1;
            else to = mid -1;
        }
        return to; // to is floor and from is ceil
    }
}

编辑于 2019-08-03 10:30:00 回复(1)
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

/**
 * @author qianyihui
 * @date 2019-07-30
 *
 * 题目描述:
 * 为了找到自己满意的工作,牛牛收集了每种工作的难度和报酬。牛牛选工作的标准是在难度不超过自身能力值的情况下,牛牛选择报酬最高的工作。
 * 在牛牛选定了自己的工作后,牛牛的小伙伴们来找牛牛帮忙选工作,牛牛依然使用自己的标准来帮助小伙伴们。
 * 牛牛的小伙伴太多了,于是他只好把这个任务交给了你。
 *
 * 输入描述:
 * 每个输入包含一个测试用例。
 * 每个测试用例的第一行包含两个正整数,分别表示工作的数量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
 * 
 * 时间复杂度是O(NlogN)。空间复杂度是O(N)。
 *
 * 运行时间:2128ms。占用内存:78688k。
 */
public class Main {
    private static class Work {
        int hard;
        int salary;
        Work(int hard, int salary) {
            this.hard = hard;
            this.salary = salary;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(), M = scanner.nextInt();
        Work[] works = new Work[N];
        for (int i = 0; i < N; i++) {
            int num1 = scanner.nextInt(), num2 = scanner.nextInt();
            works[i] = new Work(num1, num2);
        }
        //对Work按难度从易到难进行排序
        Arrays.sort(works, Comparator.comparingInt(work -> work.hard));
        //maxSalary[i]代表works数组[0, i]范围内的工资的最大值
        int[] maxSalary = new int[N];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            maxSalary[i] = Math.max(max, works[i].salary);
            max = maxSalary[i];
        }
        for (int i = 0; i < M; i++) {
            int num = scanner.nextInt();
            int index = ceil(works, num);   //寻找难度上界,ceil函数二分查找
            if (index == works.length) {    //如果说个人能力num大于所有工作的难度值
                System.out.println(maxSalary[N - 1]);   //取工资最高的那个工作
            } else if (works[index].hard > num) {   //找到了难度上界,但是该上界值大于个人能力num
                if (index == 0) {   //如果上界索引是0,这代表这个人不胜任任何工作
                    System.out.println("0");    //不胜任任何工作,其最高工资自然是0
                } else {    //否则,这个人能胜任[0, index - 1]范围内的工作
                    System.out.println(maxSalary[index - 1]);
                }
            } else if (works[index].hard == num) {  //找到了难度上界,且该上界值等于个人能力num
                System.out.println(maxSalary[index]);
            }
        }
    }

    private static int ceil(Work[] works, int hard) {
        int left = 0, right = works.length;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (works[mid].hard <= hard) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (left - 1 >= 0 && works[left - 1].hard == hard) {
            return left - 1;
        }
        return left;
    }
}

编辑于 2019-07-30 09:31:58 回复(0)
#include <iostream>
#include <algorithm>
using namespace std;
struct Work{
    int diff;//困难值
    int pay;//报酬
}jobs[100005];
/*思路:,困难值从小到大排序,然后遍历一遍,如果困难大的报酬低于难度小的,
    则更新困难大的报酬为前面值中最大的,再通过二分查找找到次小于等于结构体数组
    的困难值, 返回报酬值
    */
bool cmp(Work a,Work b){
    if(a.diff<b.diff) return true;//按困难值从小到大排序
    else if(a.diff==b.diff &&a.pay>=b.pay) return true;
    /*如果困难值相等,需要按报酬,从大到小排序,因为二分查找时,必须保证困难值相等都有
    最大的报酬值,以免查找时返回较小的报酬
    */
    return false;
}
//二分查找,找到最右边小于x困难值的报酬,logN
int find(Work jobs[],int low,int high,int x,int n){
    while(low<=high){
        int mid =(low+high)/2;
        if(jobs[mid].diff==x) return mid;
        else if(jobs[mid].diff<x) low=mid+1;
        else high=mid-1;
    }
    return high;
}
int main(){
    int N,M;
    while(cin>>N>>M){
        for(int i=0;i<N;i++) cin>>jobs[i].diff>>jobs[i].pay;
        sort(jobs,jobs+N,cmp);//按困难值从小到大排序,NlogN
        for(int i=1;i<N;i++){
            if(jobs[i].pay<jobs[i-1].pay) jobs[i].pay=jobs[i-1].pay;
        }
        int x;
        //每个伙计二分查找报酬,MlogN
        for(int i=0;i<M;i++){
            cin>>x;
            int getIndex=find(jobs,0,N-1,x,N);
            if(getIndex>=0) cout<<jobs[getIndex].pay<<endl;
            else cout<<0<<endl;//小于0,说明该伙计没有工作可以胜任
        }
    }
}

发表于 2018-09-08 15:23:35 回复(2)
#include<bits/stdc++.h>
using namespace std;

void solution(vector<pair<int,int> >& work,vector<pair<int,int> >& abilitys)
{
    sort(work.begin(),work.end(),greater<pair<int,int>>());
    sort(abilitys.begin(),abilitys.end(),greater<pair<int,int>>());
    vector<pair<int,int> > ans;
    int i = 0,j = 0;
    while(j < abilitys.size())
    {
        while(i < work.size() && work[i].second > abilitys[j].first) ++i;
        ans.push_back(pair<int,int>(abilitys[j].second,i != work.size() ? work[i].first : 0));
        j++;
    }
    sort(ans.begin(),ans.end());
    for(int i = 0; i < ans.size();++i)
        cout<<ans[i].second<<endl;
}

int main()
{
    int N,M;
    while(cin>>N>>M)
    {
        vector<pair<int,int> > work;
        vector<pair<int,int> > abilitys;
        int hard,profit,abili;
        for(int i = 0;i < N;++i)
        {
            cin>>hard>>profit;
            work.push_back(pair<int,int>(profit,hard));
        }
        for(int i = 0;i < M;++i)
        {
            cin>>abili;
            abilitys.push_back(pair<int,int>(abili,i));
        }
        solution(work,abilitys);
    }
    return 0;
}

编辑于 2018-03-28 16:16:04 回复(3)
这个题有毒
貌似测试数据中间有空行?
我机试的时候没过,
现在把中间的空行删了就过了??????????????
发表于 2018-03-28 04:14:16 回复(3)
利用map实现对工作难度的排序,只要注意难度相同的工作放入map时,要先比较两者的报酬,将value更新为较大的报酬;
然后按难度递增的顺序,更新当前工作难度所能拿到的最大报酬;
最后upper_bound找到大于小伙伴能力的第一个难度,将其迭代器位置减1,其中存放的value即为该小伙伴能拿到的最大报酬。
#include <iostream>
#include <map>
using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    map<int, int> works;
    int friends, hard=0, pay=0, maxp=0;
    for(int i=0; i<n; ++i){
        cin >> hard >> pay;
        if(works.find(hard)!=works.end() && works[hard]>=pay)
            continue;
        works[hard]=pay;
    }
    for(auto it=works.begin(); it!=works.end(); ++it){
        if(maxp > it->second){
            it->second=maxp;
            continue;
        }
        maxp=it->second;
    }
    for(int i=0; i<m; ++i){
        cin >> friends;
        cout << (--works.upper_bound(friends))->second << endl;
    }
    return 0;
}


编辑于 2020-03-20 17:02:25 回复(0)