跳转至

小美的跑腿代购#
发布于2021-04-16
上次编辑2021-04-16

问题描述#

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

格式：

输入：
- 输入第一行包含两个正整数 n，m，表示订单的数量和小美可以接的订单数量。
- 接下来有 n 行，第 i 行表示 i-1 号订单的信息。每行有两个正整数 v 和 w  ，表示一个订单的跑腿价格和商品重量。
输出：
- 输出包含 m 个 1~n 之间的正整数，中间用空格隔开，表示选择的订单编号。

示例：

输入：
     5 2
     5 10
     8 9
     1 4
     7 9
     6 10
输出：2 5

提示：

  • 1 <= n, m <= 10000
  • 1 <= v, w <= 1000

解题思路#

自定义排序。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import sys

readline = sys.stdin.readline


def readint():
    return int(readline().strip())


def readstr():
    return readline().strip()


def readints():
    return list(map(int, readline().strip().split()))


n, m = readints()
A = []
for i in range(1, n + 1):
    v, w = readints()
    A.append((-v - 2 * w, i))
A.sort()
ans = sorted([i for _, i in A[:m]])
print(*ans)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<pair<int, int>> A(n);
    for (int i = 0; i < n; ++i) {
        int v, w;
        cin >> v >> w;
        A[i] = {-v - 2 * w, i + 1};
    }
    sort(A.begin(), A.end());
    vector<int> ans(m);
    for (int i = 0; i < m; ++i) {
        ans[i] = A[i].second;
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < m; ++i) {
        cout << ans[i] << " \n"[i == m - 1];
    }
    return 0;
}
返回顶部

在手机上阅读