讨论/《美团 2021 届秋季校园招聘笔试真题》 - 小美的跑腿代购/
《美团 2021 届秋季校园招聘笔试真题》 - 小美的跑腿代购
共 10 个回复

Java堆排序

import java.util.*;
public class Solution {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        PriorityQueue<int[]> queue = new PriorityQueue<>((x, y) -> {
            if(x[1] == y[1]) return y[0] - x[0];
            else return x[1] - y[1];
        });
        for(int i = 0; i < n; ++i) {
            int v = in.nextInt();
            int w = in.nextInt();
            if(queue.size() < m) queue.offer(new int[]{i, v + w * 2});
            else if(v + w * 2 > queue.peek()[1]){
                queue.poll();
                queue.offer(new int[]{i, v + w * 2});
            }
        }
        int[] res = new int[m];
        for(int i = 0; i < m; ++i) {
            res[i] = queue.poll()[0];
        }
        Arrays.sort(res);
        for(int i : res) {
            System.out.print(i + 1 + " ");
        }
    }
}
1

计算每一份订单的收益,直接排序取前m个

#include <bits/stdc++.h>

using namespace std;


int main(int argc, char* argv[]){

    int n, m;
    cin >> n >> m;

    vector<pair<int,int>> profit(n);
    for(int i = 0; i < n; ++i){
        int a, b;
        cin >> a >> b;
        profit[i] = make_pair(a + b * 2, i+1);
    }

    sort(profit.begin(), profit.end(), [](pair<int,int>& a, pair<int,int>& b){
        if(a.first == b.first)
            return a.second < b.second;
        return a.first > b.first;
    });

    vector<int> res;
    for(int i = 0; i < m; ++i)
        res.emplace_back(profit[i].second);

    sort(res.begin(), res.end());
    for(int x : res)
        cout << x << " ";
    cout << endl;

    return 0;
}

1

java

public static void main(String[] args) {
		
		Scanner s = new Scanner(System.in);
		System.out.print("input the total number of orders and the number of order which Xiaomei can accept:");
		int num_order = s.nextInt();//储存订单的数量和小美可以接的订单数量
		int acc_order = s.nextInt();
		
		System.out.println("input the information of each order:");
        //储存每一个订单小美可以赚的钱
		ArrayList<Integer>money = new ArrayList<>(num_order);
        //储存小美可以选择的订单,也就是订单价格高的
		ArrayList<Integer>sequ = new ArrayList<>(num_order);
        
		while(true) {
			int price=s.nextInt();
			int weight = s.nextInt();
			int sum=0;
			sum=price+2*weight;
			money.add(sum);
			if(money.size()==num_order) {
				break;
			}
		}
        //找到符合条件的订单并存储在sequ中
		for(int i=0;i<money.size();i++) {
			int num=0;
			for(int j=0;j<money.size();j++) {
				 if(money.get(i)>money.get(j)) {
					 num+=1;
				 }
			}
			if(num>=num_order-acc_order) {
				sequ.add(i+1);
			}
		}
		//给sequ排序
		Collections.sort(sequ);
		System.out.println(sequ);
		
	}

1
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

struct cmp {
    bool operator()(PII a, PII b) {
        if (a.first == b.first) return a.second < b.second;
        return a.first > b.first;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    priority_queue<PII, vector<PII>, cmp> heap;
    vector<PII> res;

    for (int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;

        int t = v + w * 2;
        heap.push({t, i});

        if (heap.size() > m) heap.pop();
    }

    while (!heap.empty()) {
        res.push_back(heap.top());
        heap.pop();
    }

    sort(res.begin(), res.end(), [](PII a, PII b) {
        return a.second < b.second;
    });

    for (auto x : res) cout << x.second << " ";

    return 0;
}
import java.io.*;
import java.util.*;

class Solution {
    public static void main(String[] args) throws IOException {
        var reader = new BufferedReader(new InputStreamReader(System.in));
        var writer = new BufferedWriter(new OutputStreamWriter(System.out));

        var strings = reader.readLine().split(" ");
        int n = Integer.parseInt(strings[0]);
        int m = Integer.parseInt(strings[1]);

        Queue<int[]> heap = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0]) return Integer.compare(o2[1], o1[1]);
            return Integer.compare(o1[0], o2[0]);
        });
        List<int[]> res = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            strings = reader.readLine().split(" ");
            int v = Integer.parseInt(strings[0]);
            int w = Integer.parseInt(strings[1]);

            int t = v + w * 2;
            heap.offer(new int[]{t, i});

            if (heap.size() > m) heap.poll();
        }

        while (!heap.isEmpty()) res.add(heap.poll());

        res.sort(Comparator.comparingInt(o -> o[1]));

        for (var x : res) writer.write(x[1] + " ");

        writer.flush();
        reader.close();
        writer.close();
    }
}
1
该内容已被删除

不应该直接把前m个输出,应该对这前m个再按编号从小到大输出

1

想问一下这题新建一个实现比较的类;怎么改下面的代码???

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
import java.lang.*;
class Solution{
    private static class Item implements Comparable<Item>{
        public int id;
        public int money;
        public Item(int id, int money){
            this.id = id;
            this.money = money;
        }
        @Override
        public int compareTo(Item i){
            if(this.money == i.money){
                return this.id - i.id;
            }
            return i.money - this.money; 
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        List<Item> l = new ArrayList<Item>();
        int j = 0;
        while(true){
            Item tmp = new Item(j + 1, sc.nextInt() + 2 * sc.nextInt());
            l.add(tmp);
            j++;
            if(j == n) break;
        }
        sc.close();
        Collections.sort(l);
        for(int i = 0; i < m; i++){
            if(i != m - 1){
                System.out.print(l.get(i).id + " ");
            }else{
                System.out.println(l.get(i).id);
            }
        }
    }
    
}
/**
 * 创建一个背包,背包长度为m, 背包内使用插入排序算法,对放入背包的货物进行从大到小排序
 * 遍历商品列表,将商品有序对比背包中的货物
 *   - 如果商品价值大于背包中的货物,则插入
 *   - 如果背包没满,则插入背包尾部
 *   - 如果背包满了,则移除背包最后一个货物
 * 返回背包中的物品
 */
function getBest(n, m, list){
    var l = list.map((i, index) => {
        let p = v + 2*w
        return [p, index]
    })
    let package = []

    l.forEach(good => {
        let isInsert = false;
        for(let i = 0, len = package.length; i < len; i++) {
            if(good[0] > package[i][0]) {
                isInsert = true
                package.splice(i, 0, good)
                break;
            }
        }
        if(package.length < m && !isInsert) package.push(good)
        if(package.length > m) package.pop()
    })
    return package.map(good => good[1])
}

意思是让你忽略重量的影响

跑腿费够兰博基尼的油费吗?

谢谢~