JJOOII 2

题目链接

解题思路:分别记录每个 J, O, I 的位置然后遍历 J 的位置查找以每个 J 为起点的可以经过删除区间内元素得到所需串的最短子串,用其长度减去不需要删除的元素个数得到答案

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 0x3f3f3f3f;
const int MAX_N = 2e5 + 10;
const int MOD = 1e9 + 7;
int N, M;
char s[MAX_N];
int cntj[MAX_N], cnto[MAX_N], cnti[MAX_N];
int cj, co, ci;
void solve(){
    scanf("%d%d", &N, &M);
    scanf("%s", s);
    for(int i = 0; i < N; i++){
        if(s[i] == 'J') cntj[++cj] = i;
        else if(s[i] == 'O') cnto[++co] = i;
        else if(s[i] == 'I') cnti[++ci] = i;
    }
    if(cj < M || co < M || ci < M){
        printf("-1"); return;
    }
    int res = INF, en, lo = 1, li = 1;
    for(int i = 1; i <= cj; i++){
        if(i + M - 1 > cj) break;
        en = cntj[i + M - 1];
        while(cnto[lo] < en && lo <= co) ++lo;
        if(lo + M - 1 > co) break;
        en = cnto[lo + M - 1];
        while(cnti[li] < en && li <= ci) ++li;
        if(li + M - 1 > ci) break;
        en = cnti[li + M - 1];
        res = min(res, en - cntj[i] + 1 - 3 * M);
    }
    if(res == INF) printf("-1");
    else printf("%d", res);
}
int main(){
    int TCASE = 1;
//    scanf("%d", &TCASE);
    while(TCASE--) solve();
    return 0;
}

上一篇:用PC浏览器模拟手机浏览器(一):无扩展版


下一篇:iOS中声音采集与播放的实现(使用AudioQueue)