怎么都写的这么复杂。
DegChuZm
·
·
题解
模拟赛切了，来发儿子点的题解。
sol
手玩一下这个循环右移操作，记这个 +1-1 的前缀和数组为 s。
记这个 s 数组里的值的最小值为 mn，你考虑一次右移对这个 mn 的影响是啥。
手玩发现右移一个 + 是给所有原来是 - 的位置 +2，右移一个 - 是给所有原来是 + 的位置 -2。
那么这个时候你就发现，右移一个加号给一个减号的位置 +2，那么最小值是不是就是 +2 了？
实际上是不对的，因为一个最小值的出现一定是 +- 的一个交界处，实际上应该是最小值 +1。
同理可得如果右移的是 - 那么应该是最小值 -1。
那么这个时候就没啥难度了，你就可以枚举你用几次右移操作，然后你就知道你的最小值和总共的和了。
总共的和肯定要等于 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
---+-++--
*/
```