题目简介:
jlh很喜欢吃水果,苹果是他最喜欢的,其次是梨。他天天想着吃水果,竟然感动了女娲大神,女娲大神给了他n个篮子,让他选择其中的m个(m<=n)个篮子。每个篮子里有a个苹果和b个梨。请你们帮jlh选择篮子吧。
输入一个t(t<=10),表示有t组测试数据,再输入n和m(0=<m<=n<=100000),接下来的n行,输入a和b表示苹果和梨的数量。
Output:
按jlh选择的顺序(先选苹果多的,苹果数量相同选梨多的,两者相同选序号小的)篮子的序号(1-n),m个数用空格隔开。
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 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; 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; }
}
|