题解：CF2278C Math and Physics

· · 题解

顶级分讨题。

序列为全 1 时显然无解，否则一定有解，因为每次分裂必定会产生一个大于或等于 2 的数。

首先我们注意到，当一个序列 a 中没有 1 时，最终的答案必为 \sum a_i -1。这个结论的证明很简单，我们可以始终将中间的元素分到两侧，直到只剩两个数，这时就只能牺牲任意一个数中的一个 1 来合并了。

举个例子：序列 [2,3,4,5]。我们分裂中间的 3，得到 [3,6,5]。再分裂中间的 6，得到 [6,8]。此时无论如何都要分裂两端的数了，所以最终结果就是 6+8-1=13。

接下来考虑如何尽可能的消掉 1。

我们发现，当存在一个不在序列两端的数 a_i 使得 a_i\ge 2，那么这个序列中的 1 就全部能消掉。这个结论的证明和刚才差不多，都是始终将中间的非 1 元素分到两侧，最后总会得到两个非 1 数。

再举个例子，序列 [1,1,3,1,1]。我们分裂中间的 3，得到 [1,2,3,1]。再分裂中间的 2 和 3，得到 [4,3]，最后的结果仍然可以套用公式得到 \sum a_i -1=6。

那如果非 1 数在两端怎么办呢？我们发现，这个时候的答案就是两端的和减 1。

我们拿 [3,1,1,1] 举例。显然我们只能将 3 分裂，得到 [3,1,1]。接下来我们每次都选这个新产生的 3 进行操作，那么最后的结果就是 3。

再举一个例子：[3,1,1,4]。仿照上面的例子，我们每次都分裂两端新产生的非 1 数，那么最后剩下两个非 1 数 [3,4]，结果就是 3+4-1=6。

综上，当有解时，若存在一个不在序列两端的非 1 数，结果为 \sum a_i -1，否则为两端数之和减 1。

时间复杂度线性。

#include<bits/stdc++.h>
using namespace std;
int n,a[200005];
void solve(){
    cin>>n;
    int cnt=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        if(a[i]!=1) cnt++;
    }
    if(!cnt){
        cout<<"-1\n";
        return ;
    }
    if(cnt==1){
        if(a[1]!=1||a[n]!=1){
            cout<<max(a[1],a[n])<<'\n';
            return ;
        }
    }else if(cnt==2){
        if(a[1]!=1&&a[n]!=1){
            cout<<(a[1]+a[n])-1<<'\n';
            return ;
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++) sum+=a[i];
    cout<<sum-1<<'\n';
    return ;
}
int main(){
    int T;
    cin>>T;
    while(T--) solve();
}