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.

杰夫收到了 2n2n 个实数 a1,a2,…,a2na_1, a_2, \dots, a_{2n} 作为生日礼物。这个男孩讨厌非整数,因此他决定对收到的数字稍作“调整”。具体来说,杰夫依次执行 nn 次操作,每次操作如下:

  • 选择两个尚未被选过的下标 ii 和 jj(其中 i≠ji \neq j);
  • 将元素 aia_i 向下取整(即赋值为 ai:=⌊ai⌋a_i := \lfloor a_i \rfloor);
  • 将元素 aja_j 向上取整(即赋值为 aj:=⌈aj⌉a_j := \lceil a_j \rceil)。

然而,杰夫不想伤害送他这个序列的人的感情。因此,他希望以某种方式执行这些操作,使得操作前所有元素之和与操作后所有元素之和的绝对差值尽可能小。请帮助杰夫找出该绝对差值的最小可能值。

输入格式

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.

第一行包含一个整数 nn(1≤n≤20001 \leq n \leq 2000)。第二行包含 2n2n 个实数 a1,a2,…,a2na_1, a_2, \dots, a_{2n}(0≤ai≤100000 \leq a_i \leq 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 = 1,\, j = 4)、(i=2, j=3)(i = 2,\, j = 3)、(i=5, j=6)(i = 5,\, j = 6)。此时,差值为 ∣(0+0.5+0.75+1+2+3)−(0+0+1+1+2+3)∣=0.25|(0 + 0.5 + 0.75 + 1 + 2 + 3) - (0 + 0 + 1 + 1 + 2 + 3)| = 0.25。

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

首页