CF1806C Sequence Master

olegekei · 2023-03-21 18:04:44 · 题解

题意

给定长为 2n 的数组 p，你需要构造一个长度为 2n 的数组 q，满足 S \subseteq U 且 |S|=m ， \prod\limits_{i \in S} q_i = \sum\limits_{i \in U \setminus S} q_i 。

且你构造的 q 数组需要让 ans = \sum\limits_{i=1}^k|a_i-b_i| 最小，输出这个 ans。

思路

不难构造一个全零数组 q，即可满足题目要求。

接下来观察样例，由第一组样例发现 n=1 时容易构造 q=\{q_1,q_1\}，即可使答案最小。

由第二组样例发现 n=2 时可以构造 q=\{2,2,2,2\}，可能可以使答案最小。

第三组样例发现很难找出什么性质，甚至无法手玩出样例，此时尝试写一个爆搜程序暴力枚举 q 数组，观察样例输出 5，p=\{-2,-2,2,2\}，所以我们可以尝试将 p 数组的每个元素都加上 -5 \sim 5 来尝试得到 q 数组，当枚举出一个 q 数组时就更新一下答案。

发现最后得到的 q=\{-1,-1,-1,2\}，尝试将 n 推广到更大，发现当 n 为偶数时可以构造出 q=\{-1,-1,……,-1,n\}，而 n 为奇数时则无法构造。

最后观察第四组样例，进一步确认了 q=\{-1,-1,……,-1,n\} 的正确性。

分讨一下 n \le 2 的情况和 n 的奇偶即可。

代码

#include<cmath>
#include<iostream>
using namespace std;
int n;
long long a[400015];
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int t;
cin>>t;
while(t--){
    cin>>n;
    int m=n<<1;
    long long maxn=-1e9;
    long long ans=0,res=0;
    for(int i=1;i<=m;i++){
        cin>>a[i];
        ans+=abs(a[i]);
        if(a[i]>maxn)maxn=a[i];
    }
    if(n==1){
        cout<<abs(a[1]-a[2])<<'\n';continue;
    }
    if(n&1){
        for(int i=1;i<=m;i++){
            res+=abs(a[i]);
        }
        cout<<res<<'\n';continue;
    }
    if(n==2){
        ans=min(abs(a[1])+abs(a[2])+abs(a[3])+abs(a[4]),abs(a[1]-2)+abs(a[2]-2)+abs(a[3]-2)+abs(a[4]-2));
    }
    for(int i=1;i<=m;i++){
        res+=abs(a[i]+1);
    }
    res-=abs(maxn+1);
    res+=abs(maxn-n);
    ans=min(ans,res);
    cout<<ans<<'\n';
}
return 0;
}