[bzoj1122]账本

简化问题：如果没有2操作，答案是多少
贪心：修改-一定修改最前面的，修改+一定修改最后面的，正确性显然
而通过1操作，要完成两步：1.让最终结果为q；2.让前缀和非负，通过贪心可以获得最小值
（具体来说，假设初始有nq个+，np个-，第一步操作后前缀最小值为k，那么答案为$(|p+nq-np-q|/2+\max(p-k,0))x$）
那么枚举2操作的次数，考虑此时的答案，即要快速维护之前的贪心过程
前半部分的代价没有改变，相当于要快速维护前缀最小值
这个东西显然可以用优先队列来维护，复杂度$o(n)$
（同时要注意可能第二步的操作可以用第一步来实现（表达不清淅））

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 2000005

 4 int n,p,qq,x,y,l,r,s2,a[N],sum[N],q[N];

 5 long long ans,s1;

 6 char s[N];

 7 int main(){

 8     scanf("%d%d%d%d%d%s",&n,&p,&qq,&x,&y,s);

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

10         if (s[i-1]=='+')a[i]=a[i+n]=1;

11         else a[i]=a[i+n]=-1;

12     ans=1LL*n*x;

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

14         while ((l<r)&&(q[l]<=i-n))l++;

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

16         while ((l<r)&&(sum[i]<=sum[q[r-1]]))r--;

17         q[r++]=i;

18         if (i>=n){

19             if (i==n)s1=0;

20             else s1=n*2-i;

21             s1*=y;

22             s2=(1-p-sum[q[l]]+sum[i-n])/2;

23             if (s2<=0)ans=min(ans,s1+abs(p-qq+sum[n])/2LL*x);

24             else ans=min(ans,s1+1LL*s2*x+abs(p-qq+sum[n]+s2*2)/2LL*x);

25         }

26     }

27     printf("%lld",ans);

28 }

巴特西

[bzoj1122]账本

最新文章

热门文章