文章

20

粉丝

412

获赞

12

访问

163.2k

头像
前缀和
P1490 北京邮电大学2018年机试题
发布于2021年3月31日 21:22
阅读数 9.6k

#include <iostream>
#include <string.h>
#include <map>
using namespace std;

int main() {
    string s;
    map<int, int> m;
    int len, ans, sum[100005];
    memset(sum, 0, sizeof(sum));
    while(cin >> s) {
        ans = 0;
        len = s.length();
        sum[0] = 0;
        for(int i = 1;i <= len;i++) {
            if(s[i-1] == '1') sum[i] = sum[i-1]+1;
            else sum[i] = sum[i-1]-1;
        }
        for(int i = 0;i <= len;i++) {
            if(sum[i] == 0) ans = max(ans, i);
            else if(m[sum[i]] != 0) ans = max(ans, i-m[sum[i]]);
            else m[sum[i]] = i;
        }
        cout << ans << endl;
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发