题解 | 小红的01子序列构造（easy）

#include <iostream>
using namespace std;
//每个1前面有几个0就能得到几个01子串
//i+1时如果data[i]为0则要减去后续1数量的子串，为1则不用处理
// k超过了int32的范围，使用cin读取的话，溢出会导致后续字符串读入失败

void Quick(const string& data, int64_t n, int64_t k) {
    int64_t zCnt = 0;
    int64_t sum = 0;
    int64_t oCnt = 0;
    for(auto i = 0, j = 0; i < n-1; i++) {
        while(sum < k && j < n){
            if(data[j] == '0') {
                zCnt++;
            } else {
                if(zCnt > 0) {
                    oCnt++;
                    sum += zCnt;
                }
            }
            j++;
        }
        if(sum == k) {
            while(data[i] == '1') {
                i++;
            }
            printf("%d %d\n", i+1, j);
            return;
        }
        if(j == n && sum < k) {
            printf("-1\n");
            return;
        }
        if(data[i] == '0') {
            zCnt--;
            sum -= oCnt;
            //移除连续的1
            for(auto a = i + 1; a < j; a++) {
                if(data[a] == '1') {
                    oCnt--;
                } else {
                    break;
                }
            }
        }
    }
    printf("-1\n");
}

int main() {
    int64_t n, k;
    cin >> n >> k;
    string data;
    cin >> data;
    Quick(data, n, k);
}
// 64 位输出请用 printf("%lld")