牛牛找工作

都没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()

	#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;
}

    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]])

本套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;
}

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]));
        }
    }
}

// 懒得用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
    }
}

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;
    }
}

	

#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;
}

#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;
}

/*保持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;
}

#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;
}

#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;
}

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]])