原题链接
题目大意
现给定一个正整数$m$，然后给出一个长度为$2m$的数组$p$，请从所有的符合一定要求的长度为$2m$的数组中找到与$p$数组距离最短的数组$q$，求出两者的距离，不必解出数组$q$的每个元素的值。
数组$q$要求：从长度为$2m$数组中任意取出$m$个元素，这m个元素的积都与剩下的$m$个元素的和相等，注意是任意取$m$个元素，不是其中存在$m$个元素能够满足此条件，数学表达如下。
$$
U= \{ 1,2,…,2m \}
$$
$$
对于 \forall S\subseteq U , \left | S \right | =m 都有
$$
$$
\prod_{i \in s} q_{i} = \sum_{i \in U \setminus S} q_{i}
$$
两个数组的距离定义为两者各个下标对应元素差的绝对值再求和，也就是
$$
distance_{a,b} = \sum_{i=1}^{k} \left | a_{i} - b_{i} \right | , (\left | a \right | = \left | b \right | =k)
$$
输入样例
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}$的情况。
严格数学证明等待补充
代码
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;
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();
}
}
|
