题解：P11638 Max,Mex

如果两个操作数

x,y

进行操作，那么只有

x=0

或是

y=0

时才能让这两个数的和增加。但是，我们不仅可以把

0

变成其他数，还能把其他数（比如

1

）变为

0

！把所有的

1

变为

0

，然后和其他数配对，就是最优解。

所以，最终答案就是（假设一共有

orz

个

0

和

1

，去除了序列中的

0

和

1

之后序列的和为

ans

）：

ans+2\times orz-1

这个式子中的

-1

是因为第一个变换后的

0

（原先序列中的

0

和

1

）只能变为

1

，而其他变换后的

0

（原先序列中的

0

和

1

）能够变为

2

。

但是，这里有个坑点（hack 数据）：如果

n=1

，那么最终的答案只能是序列的和，而不是上面那个式子。

代码：

CPP

#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;
}

题解：P11638 Max,Mex

文章操作

相关推荐

评论

题解：P11638 Max,Mex