1391 01串 题目来源： Codility 基准时间限制：1 秒 空间限制：131072 KB 分值: 40 难度：4级算法题 收藏 关注 给定一个01串S,求出它的一个尽可能长的子串S[i..j]，满足存在一个位置i<=x <j, S[i..x]中0比1多，而S[x + 1..j]中1比0多。求满足条件的最长子串长度。 Input 一行包含一个只由0和1构成的字符串S。 S的长度不超过1000000。 Output 一行包含一个整数，表示满足要求的最长子串的长度。 Input示例 10 Output示例 0
sum[i]：子串[1,i]中0个数与1的个数的差
此题即是要找到一个点x使得sum[l]<sum[x]>sum[r]，其中l<x<r且r-l要尽可能的大
单调栈即可，模拟也行
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; char str[1000005]; int sum[1000005], c[2] = {1,-1}; int main(void) { int i, n, p, q, bet; scanf("%s", str+1); n = strlen(str+1); for(i=1;i<=n;i++) sum[i] = sum[i-1]+c[str[i]-'0']; p = 1, q = n; while(str[p]=='1') p++; while(str[q]=='0') q--; bet = -10000005; for(i=p;i<q;i++) bet = max(bet, sum[i]); p = n, q = 1; for(i=0;i<=n;i++) { if(sum[i]<bet) p = min(p, i), q = max(q, i); } printf("%d\n", max(q-p, 0)); return 0; }
