题目描述
Codeforces Round 935 (Div. 3) Left and Right Houses
给一个01字符串,要求一个分界线,分界线左边0得数量大于1得数量,右边1的数量大于0的数量
要求这个分界线尽量靠近中间(输出的数字右边就是分界线)
样例
input
7
3
101
6
010111
6
011001
3
000
3
110
3
001
4
1100
output
2
3
2
3
0
1
0
#include<iostream>
#include<cmath>
#pragma warning (disable : 4996)
using namespace std;
const int N = 3e5 + 10;
char str[N];
int s[N];
int n;
int main() {
scanf("%d%s", &n, str + 1); //从1读入,从0开始扫
for (int i = 1; i <= n; i++) {//统计1的前缀和
int t = str[i] - '0';
s[i] = t + s[i - 1];
}
int pos = 1e9;
for (int i = 0; i <= n; i++)
{
if (i - s[i] >= round(1.0 * i / 2) && s[n] - s[i] >= round(1.0 * (n - i) / 2)) //i-s[i]代表前面0的数量,>=i/2代表前段0的数量要大于1的数量,&&右边同理
{
if (abs(1.0 * i - 1.0 * n / 2) < abs(1.0 * pos - 1.0 * n / 2))//满足尽量靠中
{
pos = i;
}
}
}
printf("%d\n", pos);
return 0;
}