首页 > 试题广场 >

小美的跑腿代购

[编程题]小美的跑腿代购

热度指数：2027 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

小美的一个兼职是美团的一名跑腿代购员，她有n个订单可以接，订单编号是1~n，但是因为订单的时效性，他只能选择其中m个订单接取，精明的小美当然希望自己总的获利是最大的，已知，一份订单会提供以下信息，跑腿价格v，商品重量w kg，商品每重1kg，代购费用要加2元，而一份订单可以赚到的钱是跑腿价格和重量加价之和。小美可是开兰博基尼送货的人，所以自然不会在意自己会累这种事情。请问小美应该选择哪些订单，使得自己获得的钱最多。

请你按照选择的订单编号的从小到大顺序，如果存在多种方案，输出订单编号字典序较小的方案。

输入描述:

输入第一行包含两个正整数n，m，表示订单的数量和小美可以接的订单数量(1<=n,m<=10000)
接下来有n行，第i行表示i-1号订单的信息。每行有两个正整数v和w，表示一个订单的跑腿价格和商品重量。(1<=v,w<=1000)

输出描述:

输出包含m个1~n之间的正整数，中间用空格隔开，表示选择的订单编号。

示例1

输入

输出

2 5

算法知识视频讲解

JavaScript

AIcodingRobot

const [n, m] = readline().split(' ').map(Number)
let value = new Array(n).fill(0)
for(let i = 0; i < n; i++) {
    const [v, w] = readline().split(' ').map(Number)
    value[i] = {value: v + w * 2, index: i}
}
value = value.sort((a, b) => { // 对不同订单的收入进行从大到小的排序
    if(b.value !== a.value) {
        return b.value - a.value // 收入不同, 收入从大到小
    }else {
        return a.index - b.index // 收入相同, 编号从小到大
    }
})
const ans = new Array(m)
for(let i = 0; i < m; i++) {
    ans[i] = value[i].index + 1
}
console.log(ans.sort((a, b) => a - b).join(' '))

发表于 2022-05-26 00:33:43 回复(0)