[ABC173E] Multiplication 4 题解

Shunpower · 2023-03-11 17:33:36 · 题解

思路

首先注意到最好的情况就是有偶数个负数，否则算出来的乘积是负的，并不好。因此我们要极力避免选择奇数个负数的情况。

注意到当 k 为奇数的时候，只要存在至少一个正数，我就一定可以成功选择偶数个负数，而 k 为偶数的时候并不需要有正数。所以我们可以先按照是否有正数分类，再按照 k 的奇偶性分类。

关于零

注意到当 0 的个数加上 k 大于 n 时，我们无论怎么选择 k 个数总会选择到 0，因此此时答案为 0。

不存在任何正数

对于 k 为偶数的情况，显然从绝对值最大的数开始，向绝对值更小的数选择 k 个。答案即为这些数的乘积。

对于 k 为奇数的情况，显然从绝对值最小的数开始，向绝对值更大的数选择 k 个。然而这样做并不完全对，如果数列中存在 0，那么 0 显然大于这些数的乘积。因此如果数列中存在 0 答案就是 0，否则输出这些数的乘积。

存在正数

考虑 k 为奇数的情况，显然选择奇数个正数、偶数个负数更优，因此我必然会选择最大的正数。选择最大的正数并删掉它后，问题归纳为 k 为偶数。

对于 k 为偶数，选择偶数个正数、偶数个负数显然也更优，因此我们将所有正数从大到小排序，负数按照绝对值从大到小排序，然后相邻的两两组合：最大的正数和次大的正数组合，第三大和第四大组合，并以此类推。负数类似。

然后问题转变为选择乘积最大的 \frac{k}{2} 个组，贪心地将所有组处理出来按乘积从大到小排序即可。

但是这样做是有问题的。注意到负数和正数的数量可能是奇数，因此最后可能会剩余 1 个正数或负数，或者各 1 个没有成功分组。如果总的组数不足 \frac{k}{2} 那么这些剩下的数我们也必须拿来用。

剩余 1 个正数或负数是不会影响答案的，如果剩余 1 个数我们却还需要一个组，那么就说明 k>n，怎么选都选不够。

但是如果剩下的是 2 个数，那我可能必须选择这两个数来填上差的一个组。可以注意到这种情况其实就是 k=n，所以特判 k=n 即可。

对于一般情况，选择乘积最大的 \frac{k}{2} 个组时，需要注意排序组的乘积的时候不能取模后再排序，但算乘积的时候必须先模再乘，否则会爆 long long。

代码

#include <bits/stdc++.h>
#define ET return 0
#define fi first
#define se second
#define mp make_pair
#define pb emplace_back
#define ll long long
#define ull unsigned long long
#define inf INT_MAX
#define uinf INT_MIN
#define pii pair<int,int>
#define pll pair<ll,ll>
#define debug puts("--------Chery AK IOI--------");
#define Yes cout<<"Yes"<<endl;
#define No cout<<"No"<<endl;
#define pt puts("")
#define fr1(i,a,b) for(int i=a;i<=b;i++)
#define fr2(i,a,b) for(int i=a;i>=b;i--)
#define fv(i,p) for(int i=0;i<p.size();i++)
#define ld long double
#define il inline
#define ptc putchar
using namespace std;
int n,k;
vector <ll> pos,uos;
ll ans=1;
ll x;
int cnt;
const ll M=1e9+7;
vector <ll> up;
int main(){
    cin>>n>>k;
    fr1(i,1,n){
        cin>>x;
        ans*=x;
        ans%=M;
        if(x>0){
            pos.pb(x);
        }
        else if(x<0){
            uos.pb(x);
        }
        else{
            cnt++;
        }
    }
    if(cnt+k>n){//特判0太多了
        cout<<"0"<<endl;
        ET;
    }
    if(k==n){//特判k=n
        cout<<(ans+M)%M<<endl;
        ET;
    }
    sort(pos.begin(),pos.end());//正数从小到大排序
    sort(uos.begin(),uos.end());//负数从小到大排序
    if(pos.size()==0){//没有正数
        ans=1;
        if(k%2){
            if(cnt){//有0就选择0
                cout<<"0"<<endl;
                ET;
            }
            reverse(uos.begin(),uos.end());//把负数反转过来，让绝对值小的数在前面
            fr1(i,0,k-1){
                ans*=uos[i];
                ans%=M;
            }
            cout<<(ans+M)%M<<endl;
        }
        else{
            fr1(i,0,k-1){//直接从绝对值大的开始选
                ans*=-uos[i];
                ans%=M;
            }
            cout<<ans%M<<endl;
        }
    }
    else{
        ans=1;
        if(k%2){
            ans=pos[pos.size()-1];//取走最大的正数
            pos.pop_back();
            k--;
        }
        reverse(pos.begin(),pos.end());//把正数反转过来，让绝对值大的数放在前面
        fv(i,pos){
            up.pb(pos[i]*pos[i+1]);
            i++;
        }
        fv(i,uos){
            up.pb(uos[i]*uos[i+1]);
            i++;
        }//两两分组
        sort(up.begin(),up.end());
        reverse(up.begin(),up.end());//让组按乘积从大到小排序
        int l=0;
        while(k){
            ans*=up[l]%M;
            ans%=M;
            l++;
            k-=2;
        }//暴力选择前k/2个即可
        cout<<ans<<endl;
    }
    ET;
}

AC 记录