2017年NOIP普及组初赛阅读程序写结果第3题

Question

#include <iostream>
#include <string>
using namespace std;
int main()
{
    string ch;
    int a[200];
    int b[200];
    int n, i, t, res;
    cin >> ch;
    n = ch.length();
    for(i = 0; i < 200; i++) b[i] = 0;
    for(i = 1; i <= n ; i++) {
        a[i] = ch[i-1] - '0';
        b[i] = b[i-1] + a[i];
    }
    res = b[n];
    t = 0;
    for(i = n; i > 0; i--) {
        if(a[i] == 0) t++;
        if(b[i-1] + t < res) res = b[i-1] + t;
    }
    cout << res << endl;
    return 0;
}

答案为11
为什么，请提供解题思路

Answer 1

你到是给个输入啊。。。我找了一下，原题给的输入是1001101011001101101011110001
当输入字符串只由0和1构成时
不难看出a计算字符串ch中每一个字符的ASCII码和'0'的ASCII码的差，即字符串对应数组中0对应0,1对应1。所以a是字符串每一位数字构成的数组（注意是从1到n而不是从0开始）
b则是计算a数组中从1到i有多少个1
所以代码的逻辑可以分析出来，是要找到一个点，该点左侧1的个数和该点右侧0的个数加起来最小。该算法默认从最右端向左移动，寻找这样一个点，最后输出满足上述条件的个数和