题解 | 小红的01子序列构造（双指针）

#牛客春招刷题训练营# + 链接

首先要理解题意（过于简洁以至于刚开始愣了）

01子序列指的就是 "01" 这样两位，那就很显然了

计数数组辅助双指针，直接over

#include <iostream>
using namespace std;

using ll = long long;
const int MAXN=200010;
char s[MAXN];

int main() {
    int n;
    ll k, res=0;
    scanf("%d%lld",&n, &k);
    scanf("%s", (s+1));
    int cnt[2]={0};
    ++cnt[s[1]-'0'];
    bool good=false;
    for (int x=1,y=1;x<=n;++x) {
        while (y<=n && res<k) {
            ++y;
            if (s[y]=='0') {
                ++cnt[0];
            } else {
                res+=cnt[0];
                ++cnt[1];
            }
        }
        if (res==k) {
            good=true;
            printf("%d %d\n",x,y);
            break;
        }
        if (s[x]=='0') {
            res-=cnt[1];
            --cnt[0];
        } else {
            --cnt[1];
        }
    }
    if (!good) {
        puts("-1");
    }    
    return 0;
}