挺有意思的一道题
题意：给定一个\(2*n\)长度的数组\(p\),要求构造一个长度也为\(2*n\)的整数数组\(q\)，使得\(q\)满足从\(q\)中任选\(n\)个数字的积等于\(q\)中剩下\(n\)个数的和，求出\(p\)与\(q\)的最短距离
最短距离定义为对应元素差的绝对值之和
由于\(q\)的要求有点严苛，先考虑如何构造\(q\)(条件严格的话\(q\)的数量可能很小，因此后面算最小距离时可能可以暴力枚举)
分为两种情况考虑：
\(\forall i,j\)有\(q_i==q_j\)
因为其强对称性考虑全部元素都相等，此时有\(q_i^n==n*q_i\)
·得到一组通解\(q_i=0\)
·以及当\(n==1\)时，\(q_i\)可以为任意值
·当\(n==2\)时，\(q_i==2\)
当\(q_i\)不全相等时，不妨设有\(q_1!=q_2\)
此时有方程组：
\(\begin{cases}q_1*q_3*q_4*\cdots*q_{n+1}=q_2+q_{n+2}+\cdots+q_{2n}\\q_2*q_3*q_4*\cdots*q_{n+1}=q_1+q_{n+2}+\cdots+q_{2n}\end{cases}\)
两式相减得: \((q_1-q_2)*q_3*q_4*\cdots*q_{n+1}=q_2-q_1\)
即: \((q_1-q_2)*(q_3*q_4*\cdots*q_{n+1}+1)=0\)
由于\(q_1!=q_2\)，所以\(q_3*q_4*\cdots*q_{n+1}=-1\)
因为\(q\)的限制是任意\(n\)个数，所以其实\(q_{3,\cdots,2n}\)这些数中任意取\(n-1\)个的乘积都为\(-1\)
又因为\(q_i\)为整数，所以只有当\(2|n\)时，才有解：\(q_3=q_4=\cdots=q_2n=-1\)
代回方程得：\(q_1*(-1)=q_2-n+1\)
即:\(q_1+q_2=n-1\)
又有：\(q_1*q_2*\cdots*q_n=q_{n+1}+\cdots+q_{2n}\)
即：\(q_1*q_2=-n\)
解得 \(q_1=n,q_2=-1\)，无论顺序
综上，由于只有三种情况，暴力讨论距离最小值即可
点击查看代码
#include<bits/stdc++.h>
#include<vector>
#include<map>
#include<queue>
#define int long long
#define inf 1e18
#define inc 0xcfcfcfcf
#define N 300007
#define M 500007
#define mod 1000000007
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
using namespace std;
inline int Read()
{
char ch=getchar();bool f=0;int x=0;
for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
if(f==1)x=-x;return x;
}
int T=1,n,m;
bool Solve()
{
//freopen("test.in","r",stdin);
n=Read();
vector<int> a;
for(int i=1;i<=2*n;++i)
{
int in=Read();
a.emplace_back(in);
}
if(n==1)
{
printf("%lld\n",abs(a[1]-a[0]));
return 1;
}
sort(a.begin(),a.end());
int s1=0,s2=0,s3=0;
for(int i=0;i<a.size();++i)
{
s1+=abs(a[i]);
s2+=abs(a[i]-2);
if(i+1!=a.size())
s3+=abs(a[i]+1);
}
s3+=abs(a[a.size()-1]-n);
if(n==2)
{
printf("%lld\n",min(s1,min(s2,s3)));
return 1;
}
if(n%2==0)
printf("%lld\n",min(s1,s3));
else
printf("%lld\n",s1);
return true;
}
signed main()
{
T=Read();
while(T--)
if(!Solve())
printf("-1\n");
return 0;
}
/*
-std=c++11
-std=c99
*/