51nod 2517 最少01翻转次数

佚名 6年前 (2019-05-06) 随笔 606人围观抢沙发百度已收录

小b有一个01序列，她每次可以翻转一个元素，即将该元素异或上1。

现在她希望序列不降，求最少翻转次数。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。收起

输入

第一行输入一个数n，其中1≤n≤20000；
第二行输入一个由‘0’和‘1’组成的字符串

输出

输出一个非负整数，表示翻转次数

输入样例

6
010110

输出样例

2

求1的个数前缀和，枚举每一个位置，前面的1变为0，后面的0变为1，找最小值。
代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define inf 0x3f3f3f3f
using namespace std;
char s[20001];
int sum[20001];
int m = inf;
int main() {
    int n;
    scanf("%d %s",&n,s);
    for(int i = 0;i < n;i ++) {
        sum[i + 1] = sum[i] + s[i] - '0';
    }
    for(int i = 0;i <= n;i ++) {
        m = min(m,sum[i] + n - i - (sum[n] - sum[i]));
    }
    printf("%d",m);
}