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

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    string s;
    cin >> s;
    int one_cnt = 0, zero_cnt = 0;
    // k个，比如说当前lr窗口内有x个0和y个1，而且0在1之前，那么就是x*y=k
    // 右指针指向1，使用左指针统计每个1之前有几个0
    // 使用一个哈希表存储每个1之前有几个0
    int l = 0, r = 0;
    long long summ = 0;
    if (s[0] == '1') one_cnt++;
    else zero_cnt++;

    while (l < n && r < n) { // 此处不能写成对右指针的for循环自增，因为指针不能乱移！
    // 关键是要根据summ与k的大小关系对指针进行操作
        if (summ == k) {
            cout << l + 1 << " " << r + 1; // 找到满足条件的了
            return 0;
        }
        if (summ < k) {
            r++; // r++必须放在前面，保证右指针右移后，随之的summ影响得到立刻处理
            // 因为后续左指针的右移会-= one_cnt，保证右指针每个‘1’都已经改变summ
            if (s[r] == '1') {
                summ += zero_cnt; 
                one_cnt++; // '1'个数增加
            }
            else { // 如果是0对summ没有影响
                zero_cnt++; // '0'个数增加
            }
            
        }
        else if (summ > k) { // summ变多了
            if (s[l] == '1') { 
            // 左指针指向的是1，如果是1对结果没有影响，因为左指针不可能构成一个01序列
                one_cnt--;
            }
            else {
                summ -= one_cnt;
                zero_cnt--;
            }
            l++; // 无论如何，l自增
        }
    }
    cout << -1 ;
    return 0;
}