Keshawn_lu's Blog

浙工商OJ 5.jlh吃水果

字数统计: 411阅读时长: 2 min
2021/02/02 Share

题目简介:

jlh很喜欢吃水果,苹果是他最喜欢的,其次是梨。他天天想着吃水果,竟然感动了女娲大神,女娲大神给了他n个篮子,让他选择其中的m个(m<=n)个篮子。每个篮子里有a个苹果和b个梨。请你们帮jlh选择篮子吧。

Input:

输入一个t(t<=10),表示有t组测试数据,再输入n和m(0=<m<=n<=100000),接下来的n行,输入a和b表示苹果和梨的数量。

Output:

按jlh选择的顺序(先选苹果多的,苹果数量相同选梨多的,两者相同选序号小的)篮子的序号(1-n),m个数用空格隔开。

Sample Input:

1
2
3
4
5
6
7
8
9
2
2 1
2 0
1 4

3 2
3 4
2 6
3 5

Sample Output:

1
2
1
3 1

思路:

快排,自定义排序方法即可。

代码如下:

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

bool cmp(vector<int>& a, vector<int>& b) {

if (a[0] > b[0])
return true;
if (a[0] == b[0] && a[1] > b[1])
return true;
if (a[0] == b[0] && a[1] == b[1] && a[2] < b[2])
return true;

return false;
}


int main()
{

int t;
int m, n;

cin >> t;

for (int i = 0; i < t; i++) {

cin >> n >> m; //n个篮子选m个
vector<vector<int>> basket(n);

for (int j = 0; j < n; j++) {

int num1, num2;
cin >> num1 >> num2;

basket[j].push_back(num1); //苹果

basket[j].push_back(num2); //梨

basket[j].push_back(j + 1); //序号
}

sort(basket.begin(), basket.end(), cmp);

for (int k = 0; k < m - 1; k++) {

cout << basket[k][2] << " ";
}

cout << basket[m - 1][2] << endl;
}

}
CATALOG
  1. 1. 题目简介:
  2. 2. Input:
  3. 3. Output:
  4. 4. Sample Input:
  5. 5. Sample Output:
  6. 6. 思路:
  7. 7. 代码如下: