题解寿司

zero4338 · 2021-06-11 20:02:37 · 个人记录

Description

小c是一名oier .
最近 , 他发现他的数据结构好像学傻了 . 因为他在刷题时碰到了一道傻逼数据结构题 , 强行使用了平衡树来解决 , 卡着时间AC . 为此 , 他被狠狠地嘲讽了一番 . 于是 , 小c找了大量的数据结构题来做 .
昨天 , 小c正在吃寿司 , 突然发现许多盘寿司围成了一个圆圈 , 这些寿司中有红色的也有蓝色的 . 由于小c看交错的颜色非常不爽 , 想通过一些操作 , 使得所有的红色寿司形成了一块连续的区域 , 蓝色的寿司也形成了一块连续的区域 . 如果小c每次只可以交换相邻的两盘寿司 , 那么最少需要多少步才可以达到小c的要求呢 ? 由于他做题做多了 , 脑袋已经有点不清醒了 , 于是这个问题就交给你了 .

输入格式

第一行一个数T , 表示数据组数 .
接下来 T 行 , 每行一行由 B 和 R 组成的字符串 , B 表示蓝色 , R 表示红色 . 第 i 个字符描述顺时针数第 i 盘寿司的颜色 . 注意 , 最后一盘寿司和第 1 盘寿司是相邻的 .

T\leq 10,n\leq10^6

Solution

看到环 , 首先断环成链 , 对于一个序列来说 , 我们要做的就是把一种颜色放在两边 , 另一种颜色放在中间 .
因为一个蓝色在中间 , 红色在两边的方案也在其他序列中对应着一个红色在中间 , 蓝色在两边的方案 , 所以我们对一个序列只考虑红色在中间 , 蓝色在两边
设 l_i 为某个蓝色左边的红色数量 , r_i 为某个蓝色右边的红色数量
那么这个序列的答案就是

\begin{aligned}&\sum min(l_i,r_i)\\&=\sum\frac{l_i+r_i-|l_i-r_i|}{2}\\&=\sum\frac{Rnum-|l_i-r_i|}{2}\\&=Bnum* Rnum/2-\sum\frac{|l_i-r_i|}{2}\end{aligned}

其中 Bnum,Rnum 分别表示蓝色数量和红色数量 .
设 x_i=l_i-r_i
上式变为 Bnum* Rnum/2-\sum\frac{|x_i|}{2}
由于 Bnum* Rnum/2 为定值 , 我们只需使 \sum|x_i|取最大值即可求出最小花费对于最初的序列 , 我们可以 O(n) 求出所有 x_i , 由于我们要考虑所有的序列 , 之后我们要不断将序列右移 , 并求出它们的 \sum|x_i| , 也就是不断将序列最后一个颜色放到第一个 , 考虑这些移动对于 x 的影响

最后一个颜色为蓝色
一个值为 Rnum 的 x_i 的值变为 -Rnum .
最后一个颜色为红色
全体 x 的值加 2 .

也就是说 , 我们要写一种数据结构 , 支持

将一个 Rnum 的值变为 -Rnum .
全体加2
随时查询所有数的绝对值之和

考虑使用大根堆 , 维护 num0 为 x 中数值为正数的数的个数 , num1 为 x 中数值为负数的数的个数 , sum 为 x 的绝对值之和 , delta 为整个大根堆的偏移值 , 即若大根堆中有一个数为 x , 它的实际值为 x+delta
初始时我们将所有为负的 x 插入大根堆 , 并 O(n) 计算出 num1,num0,sum

操作 1

使 num0 减 1 , num1 加 1 , 并在大根堆中插入 -Rnum-delta

操作 2

使 delta 加 2 , 使 sum 变为 sum+num0* 2-num1* 2 , (分别对应正数和负数的绝对值变化)
反复取出大根堆堆顶 , 若堆顶值加上 delta 已经为正数 , 那么使 num1 减 1 , num0 加 1 , 并判断其值是否为 1 , 若是 , 那么它在这次操作前应为 -1 , 则其绝对值不应变化 , 而我们在上面更新 sum 时却把它考虑了进来 , 所以应使 sum 加 2 . 若堆顶值为负 , 则跳出循环

操作 3

维护的 sum 既是答案

所以我们一直将序列右移 , 并使用 (Rnum* Bnum-sum)/2 来更新答案即可 .

复杂度 O(nlog\ n) .

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define ll long long
using namespace std;
int read()
{
    int ret=0;char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
    return ret;
}
int abs(int x){return x>0?x:-x;}
const int maxn=1e6+5;
int T;
int n;
char s[maxn];
ll  ans;
priority_queue<int>neg;
int val[maxn];
int main()
{
    T=read();
    while(T--)
    {
        scanf("%s",s+1);
        n=strlen(s+1);
        while(neg.size())neg.pop();
        int now=0,rnum=0,bnum=0,num0=0,num1=0;
        ll sum=0;
        int delta=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='B')now++,rnum++;
            else val[i]=now,bnum++;
        }
        now=0;
        for(int i=n;i>=1;i--)
        {
            if(s[i]=='B')now++;
            else 
            {
                val[i]-=now;
                if(val[i]<0)neg.push(val[i]),num1++;
                else num0++;
                sum+=abs(val[i]);
            }
        }
        ll all=(ll)rnum*bnum;
        ans=all-sum;
        for(int i=n;i>=1;i--)
        {
            if(s[i]=='R')
            {
                num1++;num0--;
                neg.push(-rnum-delta);
            }
            else 
            {
                sum=sum+2ll*num0-2ll*num1;
                delta+=2;
                while(neg.size())
                {
                    int now=neg.top();
                    if(now+delta>=0)
                    {
                        num1--;num0++;neg.pop();
                        if(now+delta==1)sum+=2;
                    }
                    else break;
                }
                ans=min(ans,all-sum);
            }
        }
        printf("%lld\n",ans/2);
    }
    return 0;
}

题解 寿司