题解：P11638 Max,Mex

glass_goldfish · 2025-01-30 18:06:25 · 题解

如果两个操作数 x,y 进行操作，那么只有 x=0 或是 y=0 时才能让这两个数的和增加。但是，我们不仅可以把 0 变成其他数，还能把其他数（比如 1）变为 0！把所有的 1 变为 0，然后和其他数配对，就是最优解。

所以，最终答案就是（假设一共有 orz 个 0 和 1，去除了序列中的 0 和 1 之后序列的和为 ans）：

这个式子中的 -1 是因为第一个变换后的 0（原先序列中的 0 和 1）只能变为 1，而其他变换后的 0（原先序列中的 0 和 1）能够变为 2。

但是，这里有个坑点（hack 数据）：如果 n=1，那么最终的答案只能是序列的和，而不是上面那个式子。

代码：

#include<bits/stdc++.h>
#define int long long
#define INF 0x3f3f3f
using namespace std;
int n,x,ans,orz;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(x==0||x==1)orz++;
        else ans+=x;
    }
    if(n!=1&&orz!=0)cout<<ans+2*orz-1;
    else cout<<ans;
    return 0;
}