Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 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
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及/提高-
标签
枚举
点击显示
if ($pr_flag) { ?>
递交数
91
已通过
25
} ;?>
通过率
28%
时间限制
1 秒
内存限制
128 MB
来源
2018宁波初中
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和