首页 > 试题广场 >

小美的跑腿代购

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

热度指数：2020 时间限制：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

算法知识视频讲解

Python

Ivan_2021

n, m = list(map(int, input().split()))

import heapq
heap = []
hashmap = {}
for i in range(m):
    pair = list(map(int, input().split()))
    heapq.heappush(heap, pair[0]+pair[1]*2)
    if pair[0]+pair[1]*2 not in hashmap:
        hashmap[pair[0]+pair[1]*2] = [i+1]
    else:
        hashmap[pair[0]+pair[1]*2] += [i+1]
for i in range(m, n):
    pair = list(map(int, input().split()))
    if pair[0]+pair[1]*2 > heap[0]:
        if len(hashmap[heap[0]]) == 1:
            hashmap.pop(heap[0])
        else:
            hashmap[heap[0]].pop()
        if pair[0]+pair[1]*2 not in hashmap:
            hashmap[pair[0]+pair[1]*2] = [i+1]
        else:
            hashmap[pair[0]+pair[1]*2] += [i+1]
        heapq.heapreplace(heap, pair[0]+pair[1]*2)
re = []
for j in hashmap.values():
    re += j
re.sort()
print(" ".join(map(str, re)))

偷懒一波~

发表于 2021-10-01 12:07:47 回复(0)