怎么都写的这么复杂。

模拟赛切了，来发儿子点的题解。

sol

手玩一下这个循环右移操作，记这个

+1-1

的前缀和数组为

s

。

记这个

s

数组里的值的最小值为

mn

，你考虑一次右移对这个

mn

的影响是啥。

手玩发现右移一个

+

是给所有原来是 $-$ 的位置 $+2$ ，右移一个

-

是给所有原来是 $+$ 的位置 $-2$ 。

那么这个时候你就发现，右移一个加号给一个减号的位置

+2

，那么最小值是不是就是 $+2$ 了？

实际上是不对的，因为一个最小值的出现一定是

+-

的一个交界处，实际上应该是最小值 $+1$ 。

同理可得如果右移的是

-

那么应该是最小值 $-1$ 。

那么这个时候就没啥难度了，你就可以枚举你用几次右移操作，然后你就知道你的最小值和总共的和了。

总共的和肯定要等于

q

。

s_n < q

根据经典贪心暴力选最前面的

-

改，算一下它对最小值的影响。

s_n > q

其实可以不用管，你直接把末尾的加号给改成

-

一定不会使最小值变为负的。

然后每次对最小值

+2

用

2x

的代价，这个也好

O(1)

算。

做完了，复杂度

O(n)

。

但是这个地方有一点要提，如果这个

mn

是在

s_n

的，你循环右移是不会将其

-1

的。

但是这个对于我们答案完全没有影响，因为

s_n

必须要等于

q

。

代码细节有点多，我还是给一下：

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,p,q,x,y,m,ans=INT_MAX,sum,a[1000001],mxl,mxr,mn=INT_MAX;
string s;
signed main(){
//	freopen("book.in","r",stdin);
//	freopen("book.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n>>p>>q>>x>>y>>s;
//	assert(s.size()==n);
	s=" "+s;
	a[0]=p;
	for(int i=1;i<=n;i++){
		a[i]=a[i-1]+(s[i]=='+'?1:-1);
//		cout<<a[i]<<" ";
		if(i!=n) mn=min(mn,a[i]);
	}
//	cout<<'\n';
	int l=n,sm=a[n];
//	assert(!((q-sm)&1));
	for(int i=1;i<=n;i++){
		int vl=mn,val=(i-1)*y;
		if(sm<q) val+=(q-sm)/2*x,vl+=(q-sm);//改最前面的减号。 
		else if(sm>q)val+=(sm-q)/2*x;//改最后面的正号。
		if(vl>=0) ans=min(ans,val);
		else val+=(-vl+1)/2*2*x,ans=min(ans,val);
		if(s[l]=='-') mn--;
		else if(s[l]=='+')mn++;
		l--; 
	}
	cout<<ans;
	return 0;
}
/*
首先肯定要通过改位去把整个串的和给改为 p。 
9 0 3 4 1
---+-++-- 

*/

怎么都写的这么复杂。

文章操作

sol

相关推荐

评论

怎么都写的这么复杂。