CF351A.Jeff and Rounding
普及+/提高
通过率:0%
时间限制:1.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Jeff got 2_n_ real numbers _a_1, _a_2, ..., a_2_n as a birthday present. The boy hates non-integer numbers, so he decided to slightly "adjust" the numbers he's got. Namely, Jeff consecutively executes n operations, each of them goes as follows:
- choose indexes i and j (i ≠ j) that haven't been chosen yet;
- round element a__i to the nearest integer that isn't more than a__i (assign to a__i: ⌊ a__i ⌋);
- round element a__j to the nearest integer that isn't less than a__j (assign to a__j: ⌈ a__j ⌉).
Nevertheless, Jeff doesn't want to hurt the feelings of the person who gave him the sequence. That's why the boy wants to perform the operations so as to make the absolute value of the difference between the sum of elements before performing the operations and the sum of elements after performing the operations as small as possible. Help Jeff find the minimum absolute value of the difference.
杰夫收到了 2n 个实数 a1,a2,…,a2n 作为生日礼物。这个男孩讨厌非整数,因此他决定对收到的数字稍作“调整”。具体来说,杰夫依次执行 n 次操作,每次操作如下:
- 选择两个尚未被选过的下标 i 和 j(其中 i=j);
- 将元素 ai 向下取整(即赋值为 ai:=⌊ai⌋);
- 将元素 aj 向上取整(即赋值为 aj:=⌈aj⌉)。
然而,杰夫不想伤害送他这个序列的人的感情。因此,他希望以某种方式执行这些操作,使得操作前所有元素之和与操作后所有元素之和的绝对差值尽可能小。请帮助杰夫找出该绝对差值的最小可能值。
输入格式
The first line contains integer n (1 ≤ n ≤ 2000). The next line contains 2_n_ real numbers _a_1, _a_2, ..., a_2_n (0 ≤ a__i ≤ 10000), given with exactly three digits after the decimal point. The numbers are separated by spaces.
第一行包含一个整数 n(1≤n≤2000)。第二行包含 2n 个实数 a1,a2,…,a2n(0≤ai≤10000),每个数均精确到小数点后三位。这些数以空格分隔。
输出格式
In a single line print a single real number — the required difference with exactly three digits after the decimal point.
在一行中输出一个实数——所要求的差值,小数点后精确保留三位数字。
输入输出样例
输入#1
3 0.000 0.500 0.750 1.000 2.000 3.000
输出#1
0.250
输入#2
3 4469.000 6526.000 4864.000 9356.383 7490.000 995.896
输出#2
0.279
说明/提示
In the first test case you need to perform the operations as follows: (i = 1, j = 4), (i = 2, j = 3), (i = 5, j = 6). In this case, the difference will equal |(0 + 0.5 + 0.75 + 1 + 2 + 3) - (0 + 0 + 1 + 1 + 2 + 3)| = 0.25.
在第一个测试用例中,你需要执行如下操作:(i=1,j=4)、(i=2,j=3)、(i=5,j=6)。此时,差值为 ∣(0+0.5+0.75+1+2+3)−(0+0+1+1+2+3)∣=0.25。
输入解题思路,AI测评打分。不知道怎么写?