题解 P6878 【[JOI 2020 Final] JJOOII 2】

· · 题解

截至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，随后便可以确定这个串。抓住要害，简化问题。