hiho字符串 求助

0
0

这题我用二分,在最后两个测试点WA了,怎么也想不明白,请各位大侠帮忙看看哪里错了

int main(){
    boost;
    string s;
    cin >> s;
    int n = s.length();
    int l = 1, r = n;
    int ans = -1;
    while(l <= r){
        int m = (l + r) >> 1;
        bool ok = false;
        for(int i = 0; i <= n - m; ++i){
            string tmp = s.substr(i, m);    
            int c1 = 0, c2 = 0, c3 = 0;
            for(int j = 0; j < m; ++j){
                if(tmp[j] == 'h') ++c1;
                if(tmp[j] == 'i') ++c2;
                if(tmp[j] == 'o') ++c3; 
            }
            if(c1 >= 2 && c2 && c3){
                if(c1 == 2 && c2 == 1 && c3 == 1)
                    ans = m;
                ok = true;
                // break;
            }
        }
        if(ok){
            // ans = m;
            r = m - 1;
        }else{
            l = m + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

2 answer(s)

0

你怎么知道是最后两个测试点的啊

0

因为恰好俩h一o一i,不满足二分的单调性。

ok的判断条件是某一段是否有大于两个h、至少一个o和一个i,这之后再去找的恰好的时候的ans。

而某一段即使有大于两个h、至少一个o和一个i,也不一定有恰好的子串,所以可能要在更长的区间内才会有恰好的串,而二分已经不会再去尝试更长的区间了,也就不会有正确答案。

比如:

hhiiooabchaaaibbbhccco

楼主的代码会逐个测试 m = 11、5、2、3、4,而实际上最终答案是13

write answer 切换为英文 切换为中文


转发分享