A183289.成对装盒
普及-
官方
通过率:0%
时间限制:1.00s
内存限制:256MB
题目描述
有 n 件物品,第 i 件的类别编号为 ci,重量为 wi。不同类别的物品不能装在同一个盒子里。
每个类别都按以下固定规则装盒:
- 将该类别物品按重量从小到大排列。重量相同的物品谁在前都可以。
- 从左到右,每相邻两件装入一个双件盒,即第 1、2 件一盒,第 3、4 件一盒,依此类推。
- 如果该类别物品数量为奇数,最后一件单独装入一个单件盒。
每个双件盒的重量差是较重物品减去较轻物品的重量。请计算双件盒数量、单件盒数量,以及所有双件盒重量差的总和。
输入格式
第一行包含一个整数 n,表示物品数量。
接下来 n 行,第 i 行包含两个整数 ci、wi,分别表示第 i 件物品的类别编号和重量。
输出格式
输出三个整数,分别表示双件盒数量、单件盒数量和双件盒重量差的总和。
输入输出样例
输入#1
7 2 8 1 4 2 3 1 1 2 8 1 4 3 9
输出#1
2 3 8
输入#2
4 1 0 1 0 1 5 1 8
输出#2
2 0 3
说明/提示
样例 #1 解释
类别 1 的重量排序后为 1,4,4,产生一个双件盒,重量差为 3,另有一个单件盒。
类别 2 排序后为 3,8,8,产生一个双件盒,重量差为 5,另有一个单件盒。类别 3 只有一件,产生一个单件盒。
合计 2 个双件盒、3 个单件盒,重量差总和为 3+5=8。
数据范围
- 1≤n≤105。
- 1≤ci≤109,0≤wi≤109。
输入解题思路,AI测评打分。不知道怎么写?