解题：POI 2008 BBB----单调队列，贪心

· · 个人记录

题面

题外话：发现自己平时调题老下数据现在没数据不会调题了，得改改了(我不会告诉你我因为少加了个括号又乱调了4遍弄得一片WA)

先想想最直接的做法？

可以发现取反一个数会导致fsum[n] +(-)=2，而对于给定的数列和p,q，若想达到要求1，(最少的)取反次数是一定的，我们达到要求1比较容易，易得

取反次数rev= abs(((初始)fsum[n]+p-q)/2)

那要求2怎么达到？我们可以发现，对于一个确定的序列，若是p+fsum[i]≥0的要求达不到，贪心地先反转左边的-1比较好达到这个要求。在此基础上继续贪心：我们要找到fsum[i]最小的i，把i之前的k (设移动前序列最小的前缀和为t，k=(1-t)/2) (就这个括号啊啊啊啊)个-1转成1，再把后面的k个1转成-1，可以发现这样是最优的(正好满足了要求2同时依然满足要求1)

然后枚举移动操作，具体就是枚举最终的序列以哪个点开始，直接复制一份来做就吼了。枚举每个起点(当然，对于初始序列来说，不管起点怎么选反转次数都是一定的)，然后计算移动次数。这里当然是不能O(n^2)暴扫啦，因为初始这个序列的反转次数一定，只关注移动带来的影响，用单调队列维护可以优化到O(n)。至此这道吼题就做完了，细节详见代码

#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int num[2000009],fsum[2000009],cnt[2000009];//cnt[i]：以i为起点的前缀和最小值
char rd[1000009];
int n,p,q,c1,c2,minc,op,ap;
deque<int> qs;
int more(int ine)//一个计算函数
{
    int tmp=p+cnt[ine];//计算次数中...
    if(op<0) tmp+=2*ap;//初始fsum[n]<=q的情况
    return 2*((tmp<0)?(1-tmp)/2:0)+ap;//注意除法时的取整
}
int main ()
{
    scanf("%d%d%d%d%d%s",&n,&p,&q,&c1,&c2,rd);
    for(int i=0;i<n;i++)
        num[i+1+n]=num[i+1]=(rd[i]=='+')?1:-1;
    for(int i=1;i<=2*n;i++)
        fsum[i]=fsum[i-1]+num[i];
    for(int i=2*n;i;i--)//单调队列维护前缀和最小值(下标)
    {
        while(!qs.empty()&&fsum[qs.back()]>=fsum[i])
            qs.pop_back();//大的丢掉
        qs.push_back(i);//当前的进来
        while(!qs.empty()&&qs.front()>i+n)
            qs.pop_front();//找到右端点
        cnt[i]=fsum[qs.front()]-fsum[i-1];
    }
    op=(fsum[n]+p-q)/2,ap=abs(op),minc=more(1)*c1;//op：初始序列的反转操作次数，ap：计算用，常数小233，minc：答案
    for(int i=2;i<=n;i++)
        minc=min(minc,(n+1-i)*c2+more(i)*c1);//位置差(移动次数)*移动代价+反转次数*反转代价更新
    printf("%d",minc);
    return 0;
}