242027 - 移动筹码

题目描述

数轴上有 n 个筹码,第 i 个筹码的初始坐标为 x_i。多个筹码可以处于同一个坐标。
你可以对任意筹码执行以下两种操作(执行次数不限): 将筹码向左或向右移动 2 个单位,该操作免费(即坐标变为 x_i-2 或 x_i+2);
将筹码向左或向右移动 1 个单位,该操作需要花费 1 个硬币(即坐标变为 x_i-1 或 x_i+1)。
注意,允许将筹码移动到任意整数坐标,包括负数和零。 请问,将所有 n 个筹码移动到同一个坐标,最少需要花费多少个硬币?

输入

第一行包含一个整数 n(1 <= n <= 100),表示筹码的数量。
第二行包含 n 个整数 x_1, x_2, ..., x_n(1 <= x_i <= 10^9),其中 xi 是第 i 个筹码的坐标。

输出

输出一个整数,表示将所有筹码移动到同一坐标所需的最少硬币数。

样例

输入

3
1 2 3

输出

1

输入

5
2 2 2 3 3

输出

2
说明

【数据范围】 1 <= n <= 100,1 <= x_i <= 10^9
【样例说明】 在第一组样例中,一种最优方案是:将第一个筹码向右移动 2 个单位(免费),将第二个筹码向右移动 1 个单位(花费 1 枚硬币),所有筹码最终汇聚在坐标 3,最少花费为 1。
在第二组样例中,最优方案是将两个坐标为 3 的筹码分别向左移动 1 个单位(共花费 2 枚硬币),所有筹码最终汇聚在坐标 2,最少花费为 2。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 7
通过人数 5
金币数量 1 枚
难度 入门


上一题 下一题