题目链接:https://codeforces.com/contest/1806/problem/C
一个蓝名的入门题。
大意是给出一个2*N的数组,你需要构造一个数组(不需要输出),使得该数组符合任意n长度的子区间的乘积等于其他未被选择的元素的和。求是否存在一个这样的子区间,使得到原数组的路径最短。
分类讨论。
一个通解是{0,0,0,......}
对于n=1 ,有{a1,a1} 和 {a2,a2}
对于n=2 ,有{2,2} 和 {2,2}
对于任意n%2==0 ,有 {-1,-1,-1,....n},对于升序原数组。
code:
void solve(){ int n; cin>>n; for(int i=1;i<=n*2;i++){ cin>>a[i]; } sort(a+1,a+n*2+1); ll ans = 0; for(int i=1;i<=n*2;i++){ ans+=abs(a[i]); } if(n==1){ cout<<abs(a[2]-a[1])<<endl; return; } if(n==2){ ans = min({ ans, abs(a[1]-2) + abs(a[2]-2) + abs(a[3]-2) + abs(a[4]-2), abs(a[1]+1) + abs(a[2]+1) + abs(a[3]+1) + abs(a[4]-2) }); cout<<ans<<endl; return; } if(n%2==0){ ll res = 0; for(int i=1;i<n*2;i++){ res+=abs(a[i]+1); } res+=abs(a[n*2]-n); ans = min(ans,res); } cout<<ans<<endl; }