求问一道面试题

设串为a, f[i]=sum{a[i-n+1]..a[i]}(i>n) [n-1<=i<len-n] ans0[i] = Min{f[j]}(0<=j<i) - f[i+n-1] + n ans1[i] = -Max{f[j]}(0<=j<i) + f[i+n-1] + n ans[i] = Min(ans0[i], ans1[i]) ans = Min{ans[i]} Time Complexity: O(N)

【 在 fuuko 的大作中提到: 】 : 设串为a, f[i]=sum{a[i-n+1]..a[i]}(i>n) : [n-1<=i<len-n] : ans0[i] = Min{f[j]}(0<=j<i) - f[i+n-1] + n : ................... 谢谢回复 但是我还是有点不是很明白，f[i]=sum{a[i-n+1]..a[i]}(i>n) 求个和可以快速算出要改多少位，比如连续n段的和为s，改成全1的代价为 n-s，改成全0的代价为s吗？ 这个地方 感觉有点怪怪的。。: ans0[i] = Min{f[j]}(0<=j<i) - f[i+n-1] + n i+n-1是往后看n个吗？我感觉是不是应该是f[i]。。求详细解释一下，谢谢啦！

1. 最后的一串0和最后的一串1是不会相交的。所以我们可以把这个数组划成两部分，左面的这部分我们找符合要求的全0，右面的找全1。之后再反过来找一次。 2. 我们先从左往右找全0 （剩下的几种情况非常相似）。我们需要维护一个双指针状态，初始状态是左指针在0，右指针在n - 1，将两个指针之间的数变成全0的开销是k。接下来左右指针都往右移，同时维护当前子数组变成全0的开销k[i]，同时维护dp0[i]，表示此时将子数组变成全0的最小开销，这里的i代表的是右指针的位置。 （或者直接用前辍和） 3. 我们将（2）反着做一遍，即从右往右找全1。维护dp1[i]。 4. 这里我们可以得到答案min(dp0[i] + dp1[i + 1]) 5. 套用上面的算法，把数组reverse一下。得到的两次结果求最小值即可。

【 在 Wizmann 的大作中提到: 】 : 1. 最后的一串0和最后的一串1是不会相交的。所以我们可以把这个数组划成两部分，左面的这部分我们找符合要求的全0，右面的找全1。之后再反过来找一次。 : 2. 我们先从左往右找全0 （剩下的几种情况非常相似）。我们需要维护一个双指针状态，初始状态是左指针在0，右指针在n - 1，将两个指针之间的数变成全0的开销是k。接下来左右指针都往右移，同时维护当前子数组变成全0的开销k[i]，同时维护dp0[i]，表示此时将子数组变成全0的最小开销，这里的i代表的是右指针的位置。 （或者直接用前辍和） : 3. 我们将（2）反着做一遍，即从右往右找全0。维护dp1[i]。 : ................... min(dp0[i] + dp1[i + 1])這裏看不懂呀。。。

已经更新。中间有个typo 【 在 ym19940508 的大作中提到: 】 : min(dp0[i] + dp1[i + 1])這裏看不懂呀。。。

【 在 ayzmkk 的大作中提到: 】 : 谢谢回复 : 但是我还是有点不是很明白，f[i]=sum{a[i-n+1]..a[i]}(i>n) 求个和可以快速算出要改多少位，比如连续n段的和为s，改成全1的代价为 n-s，改成全0的代价为s吗？ 对的:D : 这个地方 感觉有点怪怪的。。: ans0[i] = Min{f[j]}(0<=j<i) - f[i+n-1] + n i+n-1是往后看n个吗？我感觉是不是应该是f[i]。。求详细解释一下，谢谢啦！ f[i]表示从a[i-n+1]到a[i]的和，这里表示找到一个i之前长度为n的序列变成0，加上从i开始长度为n的子段都变成1

我邮的妹子都这么厉害了么，，我特么居然不会做这题

还是不太懂[ema1]，你能把完整代码写出来么 【 在 fuuko 的大作中提到: 】 : : 对的:D : : ...................

【 在 Cabbage 的大作中提到: 】 : 还是不太懂，你能把完整代码写出来么 差不多就是窝楼上那个啦。。 ans = INT_MAX; min_all_one = max_all_one = f[n-1]; for (int i=n; i<len-n; ++i) { ans = min(ans, min_all_one - f[i+n-1]); ans = min(ans, f[i+n-1] - max_all_one); min_all_one = min(min_all_one, f[i]); max_all_one = max(max_all_one, f[i]); } ans += n;