P13707 Higher Arithmetic 题解

ARIS0_0 · 2025-11-24 08:38:21 · 题解

1. 题意解释

给出 n 个数，使用加号乘号括号组成一个合法表达式，使得表达式的值最大，你只需要输出这个表达式。

2. 思路

假如没有 1 时，我们容易知道将所有数相乘显然是更优的。

假如有 1 时，我们还需要考虑 2 的情况。

如果 1 的个数小于等于 2 的个数，我们把 1 和 2 两两相加，剩余全部相乘。

如果 1 的个数大于 2 的个数，依然是先把 1 和 2 两两配对，对剩余的 1 作讨论。

记 1 的个数为 cnt。

若 cnt=1，则将 1 与剩余数中的最小值相加。

若 cnt\equiv1\pmod 3 且 cnt\ne1，则我们拆成 \dfrac{cnt-4}{3} 个 3 和 2 个 2。

若 cnt\equiv2\pmod 3，则我们拆成 \dfrac{cnt-2}{3} 个 3 和 1 个 2。

若 cnt\equiv0\pmod 3，则我们拆成 \dfrac{cnt}{3} 个 3。

然后将所有的这些数两两相乘即可。

最后步骤就是极其麻烦的表达式输出……

Hack 数据很多，造几个 1 和 2 可以帮你查出大部分错误。

3. 代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[100100],cnt1,cnt2;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        if(a[i]==1){
            cnt1++;
        }
        if(a[i]==2){
            cnt2++;
        }
    }
    if(n==1){
        cout<<a[1];
    }
    else{
        if(cnt1<=cnt2){
            if(cnt1>0){
                if(cnt2>0){
                    cout<<"(1+2)";
                    for(int i=1;i<=cnt1-1;i++){
                        cout<<"*(1+2)";
                    }
                    for(int i=cnt1*2+1;i<=n;i++){
                        cout<<"*"<<a[i];
                    }
                }
                else{
                    cout<<a[1];
                    for(int i=2;i<=n;i++){
                        cout<<"*"<<a[i];
                    }
                }
            }
            else{
                for(int i=1;i<n;i++){
                    cout<<a[i]<<"*";
                }
                cout<<a[n];
            }
        }
        else{
            int cnt=cnt1-cnt2;
            if(cnt%3==1){
                if(cnt==1){
                    if(cnt2>0){
                        cout<<"(1+1+2)";
                        for(int i=1;i<=cnt2-1;i++){
                            cout<<"*(1+2)";
                        }
                        for(int i=1;i<=cnt/3-1;i++){
                            cout<<"*(1+1+1)";
                        }
                        for(int i=cnt1+cnt2+1;i<=n;i++){
                            cout<<"*"<<a[i];
                        }
                    }
                    else{
                        cout<<"(1+"<<a[2]<<")";
                        for(int i=3;i<=n;i++){
                            cout<<"*"<<a[i];
                        }
                    }
                }
                else{
                    if(cnt2>0){
                        cout<<"(1+2)";
                        for(int i=1;i<=cnt2-1;i++){
                            cout<<"*(1+2)";
                        }
                        for(int i=1;i<=cnt/3-1;i++){
                            cout<<"*(1+1+1)";
                        }
                        cout<<"*(1+1)*(1+1)";
                        for(int i=cnt1+cnt2+1;i<=n;i++){
                            cout<<"*"<<a[i];
                        }
                    }
                    else{
                        if(cnt/3>1){
                            cout<<"(1+1+1)";
                            for(int i=1;i<=cnt/3-2;i++){
                                cout<<"*(1+1+1)";
                            }
                            cout<<"*(1+1)*(1+1)";
                            for(int i=cnt1+cnt2+1;i<=n;i++){
                                cout<<"*"<<a[i];
                            }
                        }
                        else{
                            cout<<"(1+1)*(1+1)";
                            for(int i=cnt1+cnt2+1;i<=n;i++){
                                cout<<"*"<<a[i];
                            }
                        }
                    }
                }
            }
            if(cnt%3==2){
                if(cnt2>0){
                    cout<<"(1+2)";
                    for(int i=1;i<=cnt2-1;i++){
                        cout<<"*(1+2)";
                    }
                    if(cnt/3>0){
                        cout<<"*";
                        for(int i=1;i<=cnt/3;i++){
                            cout<<"(1+1+1)*";
                        }
                        cout<<"(1+1)";
                    }
                    else{
                        cout<<"*(1+1)";
                    }
                    for(int i=cnt1+cnt2+1;i<=n;i++){
                        cout<<"*"<<a[i];
                    }
                }
                else{
                    for(int i=1;i<=cnt/3;i++){
                        cout<<"(1+1+1)*";
                    }
                    cout<<"(1+1)";
                    for(int i=cnt1+cnt2+1;i<=n;i++){
                        cout<<"*"<<a[i];
                    }
                }
            }
            if(cnt%3==0){
                if(cnt2>0){
                    cout<<"(1+2)";
                    for(int i=1;i<=cnt2-1;i++){
                        cout<<"*(1+2)";
                    }
                    for(int i=1;i<=cnt/3;i++){
                        cout<<"*(1+1+1)";
                    }
                    for(int i=cnt1+cnt2+1;i<=n;i++){
                        cout<<"*"<<a[i];
                    }
                }
                else{
                    cout<<"(1+1+1)";
                    for(int i=1;i<=cnt/3-1;i++){
                        cout<<"*(1+1+1)";
                    }
                    for(int i=cnt1+cnt2+1;i<=n;i++){
                        cout<<"*"<<a[i];
                    }
                }
            }
        }
    }
    return 0;
}