自动搬运

查看原文

来自洛谷，原作者为

	NewJeanss **

搬运于2025-08-24 22:24:51，当前版本为作者最后更新于2020-10-29 22:22:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

截至2020年10月29日，蒟蒻暂时获得了最优解（靠运气）。

其实这道题不用想的很复杂，蒟蒻原以为是要动态规划或者搜索剪枝什么的。实际上只要 $\mathcal{O}(n)$ 即可解决。

首先，题目要求的是有顺序的的 $k$ 个 JOI 串。既然是有顺序，我们可以定位每一个 J ，从当前位置（ $x$ ）往后找最近的 $k$ 个 J ，这必然是包含 $x$ 位置时的最优解。以此类推，找到 O 和 I 即可。最终最优的串一定存在于我们所找的这些串中。

那么找最近的 $k$ 个 J ,蒟蒻一开始也傻傻的暴力往后遍历，会浪费很多时间。实际上，我们可以保存每一个 J 的位置（同理 O，I），然后直接使用 +k-1 来求后 $k$ 个 J 的那个位置。

良心不卡常不炫技代码：

#include <bits/stdc++.h>
#define N 200005
#define inf 0x3f3f3f3f
using namespace std;
int cntj[N],cnto[N],cnti[N],n,k,cj,co,ci,lo,li,end,ans;
string s;
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	while(cin>>n>>k>>s){
		s=" "+s; cj=co=ci=0;
		for(int i=1;i<=n;i++){//记录位置
			if(s[i]=='J') cntj[++cj]=i;
			if(s[i]=='O') cnto[++co]=i;
			if(s[i]=='I') cnti[++ci]=i;
		}
		lo=li=1; ans=inf;
		for(int i=1;i<=cj;i++){//遍历每一个J
			if(i+k-1>cj) break;//如果后面不足k个，跳出循环。后同理。
        		//注意lo和li不用每次从1开始，位置是单调递增的。
			end=cntj[i+k-1];
			while(cnto[lo]<=end&&lo<=co) lo++;
			if(lo+k-1>co) break;
			end=cnto[lo+k-1];
			while(cnti[li]<=end&&li<=ci) li++;
			if(li+k-1>ci) break;
			ans=min(ans,cnti[li+k-1]-cntj[i]+1-3*k);//总区间减去不用删除的长度即3*k
		}
		if(ans!=inf) cout<<ans<<endl;
		else cout<<-1<<endl;
	}
	return 0;
}

为什么会想到找 J 呢？因为整个所谓JOI串，实际上就是找 k 个 J，随后便可以确定这个串。抓住要害，简化问题。