首页 > 试题广场 >

牛牛找工作

[编程题]牛牛找工作
  • 热度指数:132681 时间限制: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

都没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-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)
#include<iostream>
#include<queue>
#include<algorithm>
#include<unordered_map>

using namespace std;
using ll = long long;
using PII = pair<ll, ll>;


const ll N = 1e5 + 5;

ll b[N];
ll c[N];
PII a[N];

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a, a + n);
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
        c[i] = b[i];
    }
    sort(b, b + m);
    unordered_map<ll, ll> ans;
    priority_queue<ll> q;
    for (int i = 0, j = 0; j < m; ++j) {
        while (i < n && a[i].first <= b[j]) {
            q.push(a[i].second);
            i++;
        }
        ans[b[j]] = q.empty() ? 0 : q.top();
    }
    for (int i = 0; i < m; ++i) {
        cout << ans[c[i]] << endl;
    }

    return 0;
}
发表于 2021-03-18 22:38:44 回复(0)
利用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)
/*保持jobs这个map中,不但难度递增,收益也是递增的;如果一个工作难度比上一个
工作高,那么就不要插入这个工作;如果插入,那么检查后面的工作是否有收益比这个工
作更低的,如果有就删除。这样的话最后查询就只需要直接找能满足能力条件的那个。删
除总量不会超过插入总量即O(n),故整个算法时间复杂度不会超过O(nlogn+n+mlogn)
,空间占用很小。*/

#include <iostream>
#include <map>
using namespace std;
int main()
{
    int N, M;
    cin >> N >> M;
    map<long, long> jobs;
    jobs.insert(make_pair(0, 0));
    for (int i = 0; i < N; i++)
    {
        long Di, Pi;
        cin >> Di >> Pi;
        auto iter = jobs.lower_bound(Di);
        iter--;
        if (iter->second > Pi)
            continue;
        iter++;
        while (iter->second < Pi && iter != jobs.end())
            iter = jobs.erase(iter);
        jobs.insert(make_pair(Di, Pi));
    }
    for (int i = 0; i < M; i++)
    {
        long Ai;
        cin >> Ai;
        cout << (--jobs.upper_bound(Ai))->second << endl;
    }
    return 0;
}

编辑于 2020-03-03 10:52:17 回复(0)
#include <bits/stdc++.h>
using namespace std;

struct Job{
    int hard;
    int money;
    Job(int h, int m){
        hard = h;
        money = m;
    }
    bool operator<(const Job& t)const{
        return hard != t.hard ? (hard < t.hard) : (money > t.money);
    }
};
int main(){
    int n, m; scanf("%d%d", &n,&m);
    vector<Job> job(n, Job(0, 0));
    for(int i=0; i<n; i++){
        int ha, mo; scanf("%d%d", &ha,&mo);
        job[i].hard = ha; job[i].money = mo;
    }
    sort(job.begin(), job.end());
    map<int, int> rmap;
    rmap[job[0].hard] = job[0].money;
    Job pre = job[0];
    for(int i=1; i<n; i++){
        if(job[i].hard != pre.hard && job[i].money > pre.money){
            rmap[job[i].hard] = job[i].money;
            pre = job[i];
        }
    }
    for(int i=0; i<m; i++){
        int key; scanf("%d", &key); 
        auto tmp = rmap.lower_bound(key);
        if(rmap.count(key) == 0) --tmp;
        cout << tmp->second << endl;
    }
    return 0;
}

发表于 2020-02-23 00:25:42 回复(0)
#include <bits/stdc++.h>
using namespace std;

struct W{
    int d, p;
};

struct P{
    int a, idx, s;
};

bool cmp1(W w1, W w2){
    return w1.d < w2.d;
}

bool cmp2(P p1, P p2){
    return p1.a < p2.a;
}

bool cmp3(P p1, P p2){
    return p1.idx < p2.idx;
}

int main(){
    int n, m;
    cin>>n>>m;
    W w[n];
    P p[m];
    for(int i=0;i<n;i++)
        cin>>w[i].d>>w[i].p;
    for(int i=0;i<m;i++){
        cin>>p[i].a;
        p[i].idx = i;
    }
    sort(w, w+n, cmp1);
    sort(p, p+m, cmp2);
    int j=0;
    for(int i=0, t=0;i<m;i++){
        for(;j<n;j++){
            if(p[i].a < w[j].d)
                break;
            t = max(t, w[j].p);
        }
        p[i].s = t;
    }
    sort(p, p+m, cmp3);
    for(int i=0;i<m;i++)
        cout<<p[i].s<<endl;
    return 0;
}

发表于 2020-01-05 01:38:17 回复(0)
import bisect
n_job,m = list(map(int,input().strip().split()))
diff_to_wage = {}
i = 0
while i < n_job:
    *** = list(map(int,input().strip().split()))
    if ***:
        diff,wage = ***
        diff_to_wage[diff] = max(diff_to_wage.get(diff,0),wage)
        i+=1
powers = []
while not powers:
    powers = list(map(int,input().strip().split())) #*** again!!
keys = sorted(diff_to_wage.keys())
for i in range(1,len(keys)):
    if diff_to_wage[keys[i]] < diff_to_wage[keys[i-1]]:
        diff_to_wage[keys[i]] = diff_to_wage[keys[i-1]]
for power in powers:
    if power in diff_to_wage: #in key time out 40%
        print(diff_to_wage[power])
    else:
        ind = bisect.bisect(keys,power)
        if not ind:
            print(0)
        else:
            print(diff_to_wage[keys[ind-1]])
发表于 2019-10-14 21:24:16 回复(1)


import java.util.Map.Entry;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {

    private static Scanner sc;

    public static void main(String[] args) {
        sc = new Scanner(System.in);
        // 读取n,m
        while(sc.hasNext()){
            int n = sc.nextInt();
            int m = sc.nextInt();
            // 给map中添加元素
            TreeMap<Integer, Integer> map = new TreeMap<Integer, Integer>();
            for (int i = 0; i < n; i++) {
                int key, val;
                key = sc.nextInt();
                val = sc.nextInt();
                // 难度系数一样,保留报酬高的
                if (map.containsKey(key) && val <= map.get(key))
                    continue;
                map.put(key, val);
            }

            // 简化map,(1,1000)和(10,1)这种,我们只要(1,1000)
            TreeMap<Integer, Integer> mapplus = new TreeMap<Integer, Integer>();
            Entry<Integer, Integer> firstentry = map.firstEntry();
            mapplus.put(firstentry.getKey(), firstentry.getValue());

            for (Entry<Integer, Integer> e : map.entrySet()) {
                if (e.getValue() > firstentry.getValue()) {
                    mapplus.put(e.getKey(), e.getValue());
                    firstentry = e;
                }
            }

//             for(Entry<Integer, Integer> e: mapplus.entrySet()){
//             System.out.println(e.getKey()+"," +e.getValue());
//             }

            // 从mapplus里面取floorkey即可
            for (int i = 0; i < m; i++) {
                int nandu = sc.nextInt();
                int key = mapplus.floorKey(nandu);
                System.out.println(mapplus.get(key));
            }
        }
        
    }
}
不通过
您的代码已保存
请检查是否存在数组越界等非法访问情况
case通过率为60.00%
谁帮我看看
发表于 2019-08-29 22:05:10 回复(0)
各位大佬,我想知道我这代码是哪里的问题?卡在80%,显示我是答案错,不是超时。
主要思路就是把朋友和工作统一起来,一起排序,然后分出朋友部分,输出。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
struct node{
	int index=0; //表示第几个朋友 
	long D;//表示能力 
	long P=0;//表示报酬 
};
node works[200004];
long a[100004];
bool temf(node n1,node n2){
	return n1.D<n2.D;
}

int main(){
	int n,m;
	while(cin>>n>>m){
		int i;
		for(i=0;i<n;i++){
			cin>>works[i].D>>works[i].P; //各种工作信息录入,index默认为0 
		}
		
		for(int j=0;j<m;j++){
			cin>>works[i+j].D; //所有朋友信息录入,报酬默认为0 ,同时录入第几个朋友 
			works[i+j].index=j;
		}
		sort(works,works+m+n,temf);//整体排序 
		int tem=0;  //存放当前能力下能得到的最大报酬 
		for(int t=0;t<m+n;t++){
			if(works[t].P >tem){
				tem=works[t].P;
			}
			if(works[t].P == 0){
				a[works[t].index]=tem;//根据朋友index填入最终的输出数组。 
			}
		}
		for(int r=0;r<m;r++){
			printf("%d\n",a[r]);//顺序输出 
		}
		
	}
	return 0;
}



发表于 2019-08-26 19:04:26 回复(0)