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

#include <iostream>
#include <cstring>
#include <string>

using namespace std;

//思路还是比较简单的，滑动窗口右边界带动左边界，因为右边界右移会使cnt_pair >= 原来的值，而左边界右移会使得cnt <= 原来的值，所以右边界使得cnt_pair >= k且左边界使得cnt_pair <= k就行了,但是代码实现还是有挺多需要注意的地方的
//注意cnt_pair可能超过int，需要long long
int main() {
	long long n, k;
	cin >> n >> k;
	char* s = new char[n + 1];
	scanf("%s", s);
  	//取-1是因为right++在处理s[right]之前，使用right = 0会导致s[0]被跳过
	int left = 0, right = -1, cnt_1 = 0, cnt_0 = 0;
	long long cnt_pair = 0;
	bool flag = false;
	while (right < n && !flag) {
		while (right < n && cnt_pair < k) {
		  	//先right++再处理s[right]是为了使得right恰好是使得cnt_pair < k的最小right,如果后right++再循环结束之后right--仍然要对边界n特判
			right++;
			if (right < n && s[right] == '1') {
				cnt_1++;
				cnt_pair += cnt_0;
			} else if (right < n && s[right] == '0') cnt_0++;
		}
		if (cnt_pair < k) break;
		while (left < n && cnt_pair > k) {
			if (left < n && s[left] == '0') {
				cnt_pair -= cnt_1;
				cnt_0--;
			} else if (left < n && s[left] == '1') cnt_1--;
			left++;
		}
		if (cnt_pair == k) flag = true;
	}
	if (flag) cout << ++left << " " << ++right << endl;
	else cout << -1 << endl;
}