题目描述
难度分:1600
输入n(1≤n≤2×105)和长为n的数组a,只包含0和1。
你按照某种顺序,标记这n个数字。
当你标记一个数字a[i]时,统计a[i]左边所有没有被标记的1的个数,和右边所有没有被标记的0的个数,加入答案。
输出答案的最小值。
输入样例1
4
0 0 1 0
输出样例1
1
输入样例2
5
1 0 1 0 1
输出样例2
3
算法
贡献法分析+枚举
没有严格证明这是最优解,但直觉上感觉就是这个结论。可以发现:
- 如果把所有的1都标记完了,剩下的0从右往左标记将不会产生任何代价;
- 同理,如果把所有0都标记完了,剩下的1从左往右标记也不会产生任何代价。
对于某个1,它会对它右边未标记的0产生贡献,也就是说在标记右边的0时,这个1会对这些0都产生代价。而对于某个0,它会对它左边未标记的1产生贡献,也就是说在标记左边的1时,这个0也会对这些1产生贡献。
因此可以预处理出数组pre,pre[i]表示[1,i]中1的个数;以及一个数组suf,suf[i]表示[i,n]中0的个数。如果要先把0标记完,就从右往左遍历原数组,只要a[i]=1,就把suf[i+1]累加到one上;如果要先把1标记完,就从左往右遍历原数组,只要a[i]=0,就把pre[i−1]累加到zero上。最终答案就是min(zero,one)。
复杂度分析
时间复杂度
遍历了两遍数组就求出了答案,时间复杂度为O(n)。
空间复杂度
开辟了pre和suf两个数组,都是线性规模的,因此额外空间复杂度为O(n)。
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 200010;
int n, a[N], pre[N], suf[N];
int main() {
scanf("%d", &n);
memset(pre, 0, sizeof pre);
memset(suf, 0, sizeof suf);
for(int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
pre[i] = pre[i - 1] + a[i];
}
for(int i = n; i >= 1; i--) {
suf[i] = suf[i + 1] + 1 - a[i];
}
LL one = 0, zero = 0;
for(int i = 1; i <= n; i++) {
if(a[i] == 1) {
one += suf[i + 1];
}
}
for(int i = n; i >= 1; i--) {
if(a[i] == 0) {
zero += pre[i - 1];
}
}
printf("%lld\n", min(one, zero));
return 0;
}