给定一个长度为n的01串,定义“连续段"为极长注续的相同字符的数量,例如001110000'有一个长度为2的0连续段,长度为3的1连续段,长度为4的0的连续段。 已知每次操作可以把一个0变成1或者把1变成0。 现在请你用最少的操作欢数,使得所有0连续段的长度都是a的倍数,1连续段的长度都是b的倍数。 输入描述:第一行输人三个正整数n, a, b 第二行输入一个长度为n的,仅有字符0和1构成的字符串,其中1<= n, a, b,<=20000. 输出描述:使得字符串合法的最小操作次数,特殊的,如果无论如何字符串都不能合法,输出-1. 示例:输入 8 2 3 10111000 输出:2. 用java给出代码
时间: 2023-05-29 16:01:17 浏览: 138
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int a = sc.nextInt();
int b = sc.nextInt();
String s = sc.next();
int cnt0 = 0; // 0连续段的长度纪录器
int cnt1 = 0; // 1连续段的长度纪录器
int ans = 0; // 操作次数
int len = 0; // 连续段长度
int flag0 = -1; // 标记下一个要匹配的0连续段的起始位置,初值设为-1
int flag1 = -1; // 标记下一个要匹配的1连续段的起始位置,初值设为-1
if(n % (a+b) != 0) { // 特判:字符串长度 不是 a + b 的倍数
System.out.println(-1);
return;
}
for(int i = 0; i < n; i++) {
if(s.charAt(i) == '0') {
if(flag0 == -1) flag0 = i; // 标记0连续段的起始位置
cnt0++;
if(cnt1 > 0 && cnt1 % b == 0) { // 1连续段长度为 b 的倍数
len = cnt1;
while(cnt0 >= a && len > 0) { // 0连续段长度为 a 的倍数
ans += 2;
cnt0 -= a;
len -= b;
}
if(len != 0) { // 无法匹配,输出-1
System.out.println(-1);
return;
} else { // 匹配成功,重置标记
flag1 = -1;
cnt1 = 0;
}
}
} else {
if(flag1 == -1) flag1 = i; // 标记1连续段的起始位置
cnt1++;
if(cnt0 > 0 && cnt0 % a == 0) { // 0连续段长度为 a 的倍数
len = cnt0;
while(cnt1 >= b && len > 0) { // 1连续段长度为 b 的倍数
ans += 2;
cnt1 -= b;
len -= a;
}
if(len != 0) { // 无法匹配,输出-1
System.out.println(-1);
return;
} else { // 匹配成功,重置标记
flag0 = 1;
cnt0 = 0;
}
}
}
}
System.out.println(ans);
}
}