CF1806C.Sequence Master
普及/提高-
通过率:0%
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
For some positive integer m , YunQian considers an array q of 2m (possibly negative) integers good, if and only if for every possible subsequence of q that has length m , the product of the m elements in the subsequence is equal to the sum of the m elements that are not in the subsequence. Formally, let U={1,2,…,2m} . For all sets S⊆U such that ∣S∣=m , i∈S∏qi=i∈U∖S∑qi .
Define the distance between two arrays a and b both of length k to be i=1∑k∣ai−bi∣ .
You are given a positive integer n and an array p of 2n integers.
Find the minimum distance between p and q over all good arrays q of length 2n . It can be shown for all positive integers n , at least one good array exists. Note that you are not required to construct the array q that achieves this minimum distance.
输入格式
The first line contains a single integer t ( 1≤t≤104 ) — the number of test cases. The description of test cases follows.
The first line of each test case contains a single integer n ( 1≤n≤2⋅105 ).
The second line of each test case contains 2n integers p1,p2,…,p2n ( ∣pi∣≤109 ).
It is guaranteed that the sum of n over all test cases does not exceed 2⋅105 .
输出格式
For each test case, output the minimum distance between p and a good q .
输入输出样例
输入#1
4 1 6 9 2 1 2 2 1 2 -2 -2 2 2 4 -3 -2 -1 0 1 2 3 4
输出#1
3 2 5 13
说明/提示
In the first test case, it is optimal to let q=[6,6] .
In the second test case, it is optimal to let q=[2,2,2,2] .