首页 > 试题广场 > 牛牛找工作
[编程题]牛牛找工作
  • 热度指数:83540 时间限制: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 回复(14)

思路

找到难度不大于能力的所有工作里,报酬最多的。核心是用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 回复(27)

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

  • 數組按難度值從小到大排序 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 回复(16)

#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 回复(1)
    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 回复(6)
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 回复(0)
使用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)
这题测试用例是真的有毒,,,有空行也不说
发表于 2018-03-28 10:46:38 回复(8)

本套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)
先吐槽牛客网的编辑器,怎么粘贴格式都不对


编辑于 2018-03-30 11:04:37 回复(5)
// 懒得用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)
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)
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)

热门推荐

通过挑战的用户

查看代码