题目
小美的一个兼职是美团的一名跑腿代购员,她有 n 个订单可以接,订单编号是 1~n ,但是因为订单的时效性,他只能选择其中 m 个订单接取,精明的小美当然希望自己总的获利是最大的,已知,一份订单会提供以下信息,跑腿价格 v ,商品重量 w kg,商品每重 1kg ,代购费用要加 2 元,而一份订单可以赚到的钱是跑腿价格和重量加价之和。小美可是开兰博基尼送货的人,所以自然不会在意自己会累这种事情。请问小美应该选择哪些订单,使得自己获得的钱最多。
请你按照选择的订单编号的从小到大顺序,如果存在多种方案,输出订单编号较小的方案。
分析
通过题目可知小美开兰博基尼送货,求小美应该选择哪些订单,使得自己陪的最少?(纯属扯淡…)
通过题目可知,这是一道排序并求top n的问题
订单排序,规则 按照收益从大到小排序,收益=v + 2 * w如果多个订单收益相同, 则按照订单号从小到大排序 输出top n订单 按照订单号从小到大的顺序
代码及解析
提供一种最小堆的解法,还有其他解法读者可自行思考完成
import java.util.ArrayList;import java.util.Collections;import java.util.List;import java.util.PriorityQueue;public class Solution {public void printOrders(int[][] orders, int count) {// 最小堆PriorityQueue<int[]> pq =new PriorityQueue<>((o1, o2) -> {// 收益小的订单排在前面,优先被poll出去;保留收益大的订单if (o1[1] == o2[1]) return o2[0] - o1[0];// 订单号大的排在前面,优先被poll出去;多笔订单具有相同收益的情况下,保留订单号小的订单return o1[1] - o2[1];});for (int i = 0; i < orders.length; i++) {// 放入最小堆pq.offer(new int[] {i + 1 /*订单号*/, orders[i][0] + 2 * orders[i][1]} /*订单收益*/);// 只保留count个收益最大的订单,poll出去多余的收益小的订单if (pq.size() > count) pq.poll();}List<Integer> numbers = new ArrayList<>();while (!pq.isEmpty()) numbers.add(pq.poll()[0]);// 按照订单号从小到大排列、输出Collections.sort(numbers);for (int num : numbers) System.out.print(num + " ");}public static void main(String[] args) {Solution solution = new Solution();int count = 2;int[][] orders =new int[][] {new int[] {5, 10},new int[] {8, 9},new int[] {1, 4},new int[] {7, 9},new int[] {6, 10}};solution.printOrders(orders, count);}}
美团届秋季校园招聘笔试真题解析:小团的复制粘贴
题目来自力扣