873B. Balanced Substring
思路
设'1' = '1' , '0' = '-1', 用sum记录前缀和,用pos数组记录a数组中前缀和等于k的第一个位置,因为前缀和表示1和0的个数差,当sum[a] == sum[b]
, (a,b]中的0和1的个数一定相同。
代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
//#define for (i, a, b) for (int i = a; i <= b; ++i)
const int N = 100004;
#define INF 0x3f3f3f3f
int n, a[N], pos[2 * N], sum[N], ans;
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; ++i)
scanf("%1d", a + i); //只读一个字符并将字符作为数字读入。
memset(pos, INF, sizeof(pos));
pos[N] = 0; // 因为pos[0]在一个都不取时为0,注意这个初始化。
for (int i = 1; i <= n; ++i)
{
sum[i] = sum[i - 1] + (a[i] ? 1 : -1); //因为运算优先级,要加括号。
if (pos[sum[i] + N] == INF)
pos[sum[i] + N] = i; //记录初始位置
else
ans = max(i - pos[sum[i] + N], ans);
}
printf("%d\n", ans);
for(int i = 1; i <= n; ++i)
printf("%d ", sum[i]);
return 0;
}