AtCoder 332 C. T-shirts (读清题意然后求解即可)
原题链接
简单
作者:
JustDoIt11
,
2023-12-11 10:59:43
,
所有人可见
,
阅读 67
package AtCoder.begin332;
import java.util.Scanner;
public class C {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt();
String s = sc.next();
int np = 0, nl = 0;
int ans = 0;
for (int i = 0; i < s.length(); i ++ ) {
if (s.charAt(i) == '0') {
ans = Math.max(ans, Math.max(np - m, 0) + nl);
np = 0;
nl = 0;
} else if (s.charAt(i) == '1') np ++ ;
else nl ++ ;
}
ans = Math.max(ans, Math.max(np - m, 0) + nl);
System.out.println(ans);
}
}
这个思路是$O(n)$的, 还有一个$O(n logn)$的思路, 二分答案, 然后枚举是否满足题意, 因为具有二段性, 所以可以过