原题链接

题目大意

现给定一个正整数m，然后给出一个长度为2m的数组p，请从所有的符合一定要求的长度为2m的数组中找到与p数组距离最短的数组q，求出两者的距离，不必解出数组q的每个元素的值。

数组q要求：从长度为2m数组中任意取出m个元素，这m个元素的积都与剩下的m个元素的和相等，注意是任意取m个元素，不是其中存在m个元素能够满足此条件，数学表达如下。

U={1,2,…,2m}
对于∀S⊆U,|S|=m都有
∏i∈sqi=∑i∈U∖Sqi

两个数组的距离定义为两者各个下标对应元素差的绝对值再求和，也就是
distancea,b=∑i=1k|ai−bi|,(|a|=|b|=k)

输入样例

plaintext
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
intput

4
1
6 9
2
1 2 2 1
2
-2 -2 2 2
4
-3 -2 -1 0 1 2 3 4

output

3  /* q=[6,6] */
2  /* q=[2,2,2,2] */
5
13

题解

首先不难发现此题中数组q的要求十分苛刻，只需分类讨论即可理清，特别是当m为偶数时多一种q=m,−1,−1,…,−1的情况。

严格数学证明等待补充

代码

c++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long LL;
// https://codeforces.com/contest/1806/problem/C
const int N=2e5+10;
// 构造题
int p[N*2],q[N*2];

void solve(){
    int n;
    LL sum=1000000e9;
    LL s=0;
    cin>>n;
    int r=n*2;
    for(int i=1;i<=r;i++) cin>>p[i];
    if(n==1){
        cout<<abs(p[1]-p[2])<<endl;
        return;
    }
    else if(n&1){
        sum=0;
        for(int i=1;i<=r;i++) sum+=abs(p[i]);
        cout<<sum<<endl;
        return;
    }
    else{
        s=0;
        sort(p+1,p+1+r);
        memset(q,-1,sizeof q);
        q[r]=n;
        for(int i=1;i<=r;i++){
            s+=abs(p[i]-q[i]);
        }
        sum=min(s,sum);

        s=0;
        for(int i=1;i<=r;i++) s+=abs(p[i]);
        sum=min(sum,s);
    }

    if(n==2){
        s=0;
        for(int i=1;i<=r;i++){
            s+=abs(p[i]-2);
        }
        sum=min(sum,s);
    }
    cout<<sum<<endl;
}

int main(){
    fastIO
    int t;
    cin>>t;
    while(t--){
        solve();
    }
}