Description：

给定一个由 $+1$ 和 $−1$ 构成的长度为 $n$ 的序列，提供两种操作：

$1.$ 将某一位取反，花销为 $x$ 。 $2.$ 将最后一位移动到第一位，花销为 $y$ 。

要求最终 $p+sum=q$ ，且 $\forall i\in[1,n]p+sum_i\geqslant0$ ，求最小花销。

$1\leqslant n \leqslant 10^6$

Solution：

循环移位非常不好处理，这题的做法是断环成链，把环复制两倍，也就是说暴力枚举移位，这样移位的代价是可以计算出的，剩下的代价还有两部分，保证序列所有位置为正和最终结果为 $q$ ，对于第一部分，发现只要让当前前缀和最小的位置前缀和为正了，就一定有一种方案让整个前缀和序列为正，设最小的前缀和为 $k$ ，这个可以单调队列求出，那么这部分的花销是 $\lceil\frac{-k} 2\rceil$ ，因为改变一个位置的值会产生 $2$ 的变化，当前序列的总和是 $sum[n]+p+\lceil\frac{-k}2\rceil\times 2$ ，要想让它变成 $q$ ，就要再付出他们的差值除二上取整乘 $x$ 的花费，最后和答案取 $\min$ 即可，复杂度 $O(n)$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<cstring>

using namespace std;

int n,p,q,x,y;

#define MAXN 2000010

inline char getc()

{

	register char c = getchar();

	while(c != '-' && c != '+')c = getchar();

	return c;

}

int a[MAXN],sum[MAXN];

int main()

{

	scanf("%d%d%d%d%d",&n,&p,&q,&x,&y);

	for(int i = 1;i <= n;++i)

	{

		if(getc() == '-')a[i] = -1;

		else a[i] = 1;

	}

	for(int i = n + 1;i <= 2 * n;++i)

	{

		a[i] = a[i - n];

	}

	sum[0] = p;

	for(int i = 1;i <= 2 * n;++i)

	{

		sum[i] = sum[i - 1] + a[i];

	}

	deque<int> qu;

	for(int i = 1;i < n;++i)

	{

		while(!qu.empty() && sum[i] <= sum[qu.back()])qu.pop_back();

		qu.push_back(i);

	}

	int ans = 0x3f3f3f3f;

	for(int i = n;i < 2 * n;++i)

	{

		while(!qu.empty() && sum[i] <= sum[qu.back()])qu.pop_back();

		qu.push_back(i);

		while(!qu.empty() && qu.front() <= i - n)qu.pop_front();

		int val = sum[qu.front()] - sum[i - n] + p;

		int res = 0;

		res += (n - (i - n)) % n * y;

		if(val < 0)res += (-val + 1) / 2 * x;

		int cur = sum[n];

		if(val < 0)cur += (-val + 1) / 2 * 2;

		res += (abs(cur - q) + 1) / 2 * x;

		ans = min(ans,res);

	}

	cout << ans << endl;

	return 0;

}