题解 P2697 【宝石串】

peterwuyihong · 2019-08-16 18:07:15 · 题解

其实这道题可以用二分

二分答案长度，再字符串中操作即可

过程详见代码

#include<bits/stdc++.h>
using namespace std;
char s[1000005];
int len,l=1,r;
bool check(int x)
{
    int R=0,G=0;//R,G都是0
    for(int i=1;i<=x;i++)
    R+=(s[i]=='R'),G+=(s[i]=='G');
   //初始字符串的R与G值
    if(R==G)return 1;//先判断一下
    for(int i=x+1,j=1;i<=len;i++,j++)
    {
        if(s[j]=='R')R--;
        if(s[j]=='G')G--;//去掉字符串头
        if(s[i]=='R')R++;
        if(s[i]=='G')G++;//加入字符串尾
        if(R==G)return 1;//成功直接退出
    }
    return 0;//不成功
}
int main()
{
    scanf("%s",s+1);
    len=strlen(s+1);
    r=len/2;//由于奇数不行,便二分偶数
    while(l<=r)
    {
        int mid=(l+r)>>1;
    //  printf("%d %d %d\n",l,mid,r);
        if(check(mid<<1))l=mid+1;
        else r=mid-1;
    }
    printf("%d",r<<1);//答案是2倍
}

算法复杂度O(|S|\log\frac{|S|}2)