P6878 [JOI 2020 Final] JJOOII 2 题解

Problem Link

Explanation

给定一个只包含 $\tt J$、$\tt O$、$\tt I$ 三种字符、长度为 $N$ 的字符串 $S$ 和一个正整数 $K$。定义 $K$ 阶 $\tt JOI$ 串为由恰好 $K$ 个 $\tt J$ 、$K$ 个 $\tt O$ 、$K$ 个 $\tt I$ 依次拼接而成的字串。如 $2$ 阶 $\tt JOI$ 串为 $\tt JJOOII$ 。你可以对 $S$ 进行任意次以下操作以将 $S$ 变为 $K$ 阶 $\tt JOI$ 串：

1. 删除 $S$ 的第一个字符
2. 删除 $S$ 的最后一个字符
3. 删除 $S$ 的任意一个字符

要求最小化并输出第三种操作的次数。如果不能将 $S$ 变为 $K$ 阶 $\tt JOI$ 串，输出 -1 。

Solution

可以发现只要定位到了最前端的 $\tt J$ 的位置，那么就可以确定一个最短的 $\tt JOI$ 串。

即我们可以暴力从前向后扫 $\tt J$ 的位置，然后依次找到 $K$ 个 $\tt O$ 和 $\tt I$ 即可。

可以对上面的算法进行优化，我们记录每个 $\tt J$、$\tt O$、$\tt I$ 的位置为 cj、co、ci，那么一段 $\tt J$ 的开始位置即为 $cj_j$，结束位置为 $cj_{j+k-1}$，$\tt O$，$\tt I$ 同理。

Core Code

int n,k;
char s[N];
int cj[N],co[N],ci[N];
int totj,toto,toti;
int ans=INF;
int main()
{
	n=read();k=read();
	scanf("%s",s+1);
	for(int i=1;i<=n;i++)
	{
		if(s[i]=='J') cj[++totj]=i;
        if(s[i]=='O') co[++toto]=i;
        if(s[i]=='I') ci[++toti]=i;
	}
    for(int i=1;i<=totj;i++)
    {
        if(i+k-1>totj) break;//后面不足 k 个 j，下面 o,i 同理
        int ed=cj[i+k-1];//一段 j 的结束，下面 o,i 同理
        int pos=1;
        while(co[pos]<=ed && pos<=toto) pos++;//o 的起始位置，下面 i 同理
        if(pos+k-1>toto) break;
        ed=co[pos+k-1];
        pos=1;
        while(ci[pos]<=ed && pos<=toti) pos++;
        if(pos+k-1>toti) break;
        ed=ci[pos+k-1];
        ans=min(ans,ed-cj[i]+1-3*k);//答案为枚举的区间长度与 3*k 的差
    }
    printf("%d\n",(ans==INF)?-1:ans);
	return 0;
}