文章

25

粉丝

364

获赞

8

访问

207.9k

头像
字符串翻转
P1642 杭州电子科技大学机试题
发布于2021年2月18日 23:30
阅读数 8.3k

思路:遇1见一,遇0加一 ,和最大子列和差不多

/*
 *  Description: 字符串区间翻转 (http://noobdream.com/DreamJudge/Issue/page/1642/)
 *  Author: 鱼翔浅底
 *  Date: 2021-02-18 22:57:14
 */
#include <cstdio>
#include <cstdlib>

using namespace std;

//翻转后得到的最多1的个数
int StringFlip(char s[], int N)
{
    int cnt = 0, max = 0, tmp = 0;

    for (int i = 0; i < N; i++)
    {
        if (s[i] == '1')
        {
            cnt++;                               //计算原来1的个数
            tmp = (tmp - 1 < 0) ? 0 : (tmp - 1); //翻转1-->0
        }
        else //翻转0-->1
        {
            tmp++;
            max = (tmp > max) ? tmp : max;
        }
    }

    return (cnt + max);
}

int main()
{
    int N;
    char s[10000000];

    while (~scanf("%d", &N))
    {
        scanf("%s", s);

        printf("%d\n", StringFlip(s, N));
    }

    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发