问题 4221 --1. 汪星人的身高 (height)

4221: 1. 汪星人的身高 (height)

题目描述

汪星是一个崇尚和谐和公平的星球。一天汪星人的国王发现汪星人的身高出现了不同程度的差异,表示非常担心,于是他希望改变其中一些人的身高来保持星球的和谐与公平。 汪星人也分为男性和女性,国王觉得所有男性的身高应该一样,所有女性的身高也应该一样,但男性和女性的身高不一样。所以国王希望改变尽可能少的人的身高来达到这个目标。 请编程计算国王至少需要改变多少个人的身高才能达到目标。

输入

输入共 2n+1 行。 第 1 行一个整数 n,表示汪星人上分别有 n 名男性和 n 名女性。 接下来 2n 行,每行两个整数。其中第 i+1 行的两个整数分别表示第 i 位汪星人的性别和身高,其中男性用 1 表示,女性用 0 表示。

输出

输出 1 行一个整数,表示至少需要改变多少个人身高才能满足要求。

样例输入输出

输入#1 复制
2
1 170
0 162
1 170
0 161
输出#1 复制
1
输入#2 复制
1
1 172
0 164
输出#2 复制
0
输入#3 复制
3
1 170
0 170
0 170
1 170
1 170
0 170
输出#3 复制
3

提示

【样例 1 解释】 在样例 1 中,两名男性的身高都是 170,已经达到目标,不需要改变,但两名女性的身高有所差异,改变其中任何一个人的身高都可以达到目标。 【样例 2 解释】 在样例 2 中,只有一名女性和一名男性,男性和女性的身高都不需要改变就已经达到目标。 【样例 3 解释】 在样例 3 中,3 名男性和 3 名女性的身高都是 170,不满足国王对男性身高和女性身高不一样的目标,所以至少要改变 3 名男性或者 3 名女性的身高才能达到国王的目标。 【数据范围约定】 测试点编号  n  身高 10~30%  1≤n≤100 40%~100%  $1≤n≤10^5$ 120≤身高≤200
序号 标题 作者 发表时间 费用 订购数 操作