Choice 题解

我们依次考虑两个操作怎么实现。

不难发现，对于一个确定的‘+’‘-’序列，需要更改的次数是一定的。

那么我们现在只有交换一个操作，满足非负一个限制。

对于交换操作，我们可以倍长序列，枚举从哪里开始交换。

相当于是 $2q$ 序列上的长为 $q$ 的区间。

将这个区间到末尾所有的位置提到前面去。

那么如何判断是否合法呢，要利用前缀和。

如果前缀和最小的位置的答案非负，那么一定合法。

反之，我们就要进行一定的‘1’操作，使其非负。

找到固定区间长度的最小值，使用单调队列。

注意：在修改序列的值后，仍要满足最后的值等于m的条件。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1e6+9;
int q,n,m,v1,v2,ans=0x7f7f7f7f,cnt;
char ch[N];
int a[N*2],Q[N*2],hh,tt,sum[N*2];
bool flag=true;
int main()
{
	// freopen("choice.in","r",stdin);
	// freopen("choice.out","w",stdout); 
	scanf("%d%d%d%d%d",&q,&n,&m,&v1,&v2);
	scanf("%s",ch+1);
	for(int i=1;i<=q;i++)
	{
		if(ch[i]=='+') a[i]=a[i+q]=1;
		else a[i]=a[i+q]=-1;
	}
	for(int i=1;i<=q*2;i++) 
		sum[i]=sum[i-1]+a[i];
	for(int i=1;i<=q;i++)
	{	
		while(hh<=tt&&sum[Q[tt]]>=sum[i]) --tt;
		Q[++tt]=i;//先找到原序列的最小值，备用
	}
	for(int i=q;i<=q*2;i++)
	{
		while(hh<=tt&&i-Q[hh]>=q) ++hh;
		while(hh<=tt&&sum[Q[tt]]>=sum[i]) --tt;
		Q[++tt]=i;
		int now=n+sum[Q[hh]]-sum[i-q];//now表示此时能到达的最小值
		int val=0,p=n+sum[i]-sum[i-q];//p是没有操作完成后的值
		if(now<0)
		{//上取整
			val=(-now+1)/2*v1;
			p+=(-now+1)/2*2;//更改了一些数，对p也有影响
		}
		int tmp=val+abs(p-m)/2*v1;//最后答案修正为m的代价
		if(i!=q) tmp+=v2*(2*q-i);//把i以后的数全部提前的代价
		ans=min(ans,tmp);
	}
	printf("%d\n",ans);
	return 0;
}