首页 > 试题广场 >

小红的01子序列构造(easy)

[编程题]小红的01子序列构造(easy)
  • 热度指数:6179 时间限制:C/C++ 3秒,其他语言6秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个仅由字符 \tt 0,1 组成的字符串 s,长度为 n。小红想找到一个闭区间 [l,r] 使得在子串 s_{l..r} 中,恰好存在 k 个严格等于 01子序列(即选取下标 i<j,满足 s_i=\texttt{0},\ s_j=\texttt{1})。
\hspace{15pt}请你输出任意一个满足条件的区间;若不存在,则输出 -1

【名词解释】
\hspace{15pt}子序列:从字符串中删除任意个(可为零)字符后得到的字符串,保留剩余字符原有相对顺序。

输入描述:
\hspace{15pt}第一行输入两个整数 n,k\left(1\leqq n\leqq 2\times10^{5};\ 1\leqq k\leqq 10^{10}\right)——字符串长度与目标子序列数量。 
\hspace{15pt}第二行输入一个长度为 n 的 01 串 s(下标从 1 开始)。


输出描述:
\hspace{15pt}若不存在满足要求的区间,输出单独一行-1;否则输出两个整数 l,r\left(1\leqq l\leqq r\leqq n\right) 表示区间端点(输出任意一组均可)。
示例1

输入

4 2
0011

输出

1 3

说明

子串 s_{1..3}=\texttt{ 内的 01 子序列共有 2 个:s_1s_3s_2s_3
示例2

输入

4 2
1110

输出

-1
#参考双指针思路
n, k = map(int, input().split())
s = input().strip()

if n == 0:
    print(-1)
    exit()

cnt0 = 0
cnt1 = 0
l = 0
r = 0

# 初始化第一个字符
if s[0] == '0':
    cnt0 += 1
elif s[0] == '1':
    cnt1 += 1

num = 0
result = None

while l < n and r < n:
    if num == k:
        result = (l + 1, r + 1)
        break
    if num < k:
        # 移动右指针
        if r + 1 < n:
            r += 1
            current_char = s[r]
            if current_char == '0':
                cnt0 += 1
            else:
                num += cnt0
                cnt1 += 1
        else:
            # 无法移动右指针时,尝试移动左指针
            current_char = s[l]
            if current_char == '0':
                num -= cnt1
                cnt0 -= 1
            else:
                cnt1 -= 1
            l += 1
    else:
        # 移动左指针
        current_char = s[l]
        if current_char == '0':
            num -= cnt1
            cnt0 -= 1
        else:
            cnt1 -= 1
        l += 1

# 检查退出循环后是否满足条件
if result is None and num == k and l <= r < n:
    result = (l + 1, r + 1)

if result:
    print(result[0], result[1])
else:
    print(-1)

发表于 2025-04-14 15:07:30 回复(0)