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

我们将使用滑动窗口来解决这个问题

使用L，R两个变量来维护这个滑动窗口，使用cnt1与cnt0来记录窗口内部的0的个数以及1的个数由于区间左侧的1以及区间右侧的0都不会发挥作用，因此就根据是否有效来使用while循环选择性将他们移除

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

void solve()
{
    ll n,k;cin>>n>>k;
    string s;cin>>s;
    // 每次左侧指针向右移动就减掉那个位置以后到r为止的1，
    // 右侧指针向左移动就减掉那个位置之前到l为止的0
    ll l = 1,r = 1,cnt0 = 0,cnt1 = 0;
    ll sum = 0;
    while (true)
    {
        if(sum ==  k) 
        {
            cout<<l<<' '<<r-1<<'\n';
            return ;
        }
        else if (sum < k)
        {
            while (r <=n &&s[r-1] == '0') r++,cnt0++;
            if (r > n) break;
            sum+=cnt0;cnt1++;
            r ++;
        }
        else      
        {
            while (l <= n&&s[l-1] == '1') l++,cnt1--;
            if (l >=n)  break;
            sum -= cnt1;cnt0--;
            l ++;
        }
        // 通过移动r来扩展区间
        // 通过移动l来收缩区间
    }
    cout<<-1<<'\n';
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);solve();return 0;}