怎么会有那么多病毒

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 1 总提交人数: 2

题目介绍

公元20202年,世界各地同时爆发了 $n$ 种病毒。而人类的科研能力有限,在有限的时间内只能研制 $m$ 种病毒的解药。为此,我们希望对威胁能力最高的 $m$ 种病毒进行解药研制,以尽可能拯救生命。

每种病毒具有三种基本指标:传染性、病毒症状、病毒能力,三种指标都是正整数。我们认为病毒的威胁指数为三者之和,即威胁性=传染性+病毒症状+病毒能力。

你需要编写程序来快速完成这项工作:即求出前 $m$ 种(若 $n>m$ 则输出 $m$ 种,若 $n<m$ 那么只输出 $n$ 种就可以)最具威胁性的病毒的各项基本指标分别是多少。

输入格式

第一行两个数,用空格隔开:$n$ 和 $m$,如题所述。

接下来n行,每行有三个数 $a_i$,$b_i$,$c_i$,表示一种病毒的传染性、病毒症状、病毒能力指数。

输出格式

程序的输出应有 $\min(n,m)$ 行。

第 $i$ 行表示威胁性第 $i$ 大的病毒的三种基本指标。

输入样例

3 2
1 1 5
1 2 6
10 1 3

输出样例

10 1 3
1 2 6

样例解释

一共有三种病毒,可以研制两种解药。

所以选择威胁性最高的"10+1+3"和"1+2+6"两种病毒来研制解药。

数据范围

$1 \leq n \leq 100,000, 1 \leq m \leq 100,000$。

对任意的i有:$1 \leq a_{i}, b_{i}, c_{i} \leq 100,001$。

数据保证任意两种病毒的威胁性不同。

HINT

测试数据中将存在 $n>m$,$n<m$,以及 $n=m=100,000$ 各种情况的数据,提交代码前请考虑周全。

虽然重头是排序方法,但仍建议使用结构体(struct)来使思路更清晰,代码更具可读性。

病毒的威胁性各不相同可以保证输出答案的唯一性,但这个条件可能不仅仅是为了保证这一点。

AUTHOR:康时嘉

相关推荐