A183290.分类入围
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
有 n 个报名项目。每个项目都有互不相同的编号 idi,以及类别编号 ci、得分 si 和用时 ti。
每个类别最多选出 k 个项目入围。各类别独立选择,顺序按以下规则确定:
- 先比较得分,得分高的在前。
- 得分相同时,才比较用时,用时少的在前。
- 得分和用时都相同时,才比较项目编号,编号小的在前。
每类取排在最前面的 k 个项目;不足 k 个时全部入围。最终将所有入围项目的编号从小到大输出。项目编号的大小与输入顺序没有关系。
输入格式
第一行包含两个整数 n、k,分别表示项目数量和每个类别的入围数量上限。
接下来 n 行,每行包含四个整数 idi、ci、si、ti,分别表示第 i 个输入项目的编号、类别编号、得分和用时。
输出格式
第一行输出入围项目总数。第二行按编号从小到大的顺序输出所有入围项目编号,相邻编号之间用一个空格分隔。
输入输出样例
输入#1
6 2 40 1 90 5 10 1 90 5 30 1 90 4 25 2 80 2 5 2 85 9 50 3 0 0
输出#1
5 5 10 25 30 50
输入#2
4 1 99 7 10 1 2 7 11 8 8 9 5 3 1 9 5 3
输出#2
2 1 2
说明/提示
样例 #1 解释
类别 1 的选择顺序为编号 30、10、40:30 的用时更少;10 与 40 得分和用时相同,按编号决定先后。该类入围 30、10。
类别 2 只有两个项目,类别 3 只有一个项目,均全部入围。将五个入围编号重新按从小到大排列,得到 5 10 25 30 50。
数据范围
- 1≤n≤105,1≤k≤5。
- 1≤idi,ci≤109,所有 idi 互不相同。
- 0≤si,ti≤109。
输入解题思路,AI测评打分。不知道怎么写?