A183289.成对装盒

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:256MB

题目描述

有 nn 件物品,第 ii 件的类别编号为 cic_i,重量为 wiw_i。不同类别的物品不能装在同一个盒子里。

每个类别都按以下固定规则装盒:

  1. 将该类别物品按重量从小到大排列。重量相同的物品谁在前都可以。
  2. 从左到右,每相邻两件装入一个双件盒,即第 11、22 件一盒,第 33、44 件一盒,依此类推。
  3. 如果该类别物品数量为奇数,最后一件单独装入一个单件盒。

每个双件盒的重量差是较重物品减去较轻物品的重量。请计算双件盒数量、单件盒数量,以及所有双件盒重量差的总和。

输入格式

第一行包含一个整数 nn,表示物品数量。

接下来 nn 行,第 ii 行包含两个整数 cic_i、wiw_i,分别表示第 ii 件物品的类别编号和重量。

输出格式

输出三个整数,分别表示双件盒数量、单件盒数量和双件盒重量差的总和。

输入输出样例

  • 输入#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 解释

类别 11 的重量排序后为 1,4,41,4,4,产生一个双件盒,重量差为 33,另有一个单件盒。

类别 22 排序后为 3,8,83,8,8,产生一个双件盒,重量差为 55,另有一个单件盒。类别 33 只有一件,产生一个单件盒。

合计 22 个双件盒、33 个单件盒,重量差总和为 3+5=83+5=8。

数据范围

  • 1≤n≤1051\le n\le10^5。
  • 1≤ci≤1091\le c_i\le10^9,0≤wi≤1090\le w_i\le10^9。

输入解题思路,AI测评打分。不知道怎么写?

首页