Codeforces 383A Milking cows(贪心)

题目链接:Codeforces 383A Milking cows


题目大意:一个农场有n头奶牛,现在农场主要挤奶,0代表朝左,1代表朝右。如果奶牛看到其他奶牛被挤奶的话,会受到惊吓,产奶量会减少1。问说一个序列使得损失最少。


解题思路:先将脸朝左的按照从右到左的顺序挤掉,再将朝右的按照从左到右挤掉。损失数只要计算前缀和即可。


#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>

using namespace std;
typedef long long ll;
const int N = 200005;

int n, cow[N];
ll s[N];

void init () {
	memset(s, 0, sizeof(s));

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &cow[i]);
		s[i] = s[i-1] + (cow[i] == 1 ? 1 : 0);
	}
}

ll solve () {
	ll ans = 0;
	for (int i = n; i; i--) if (cow[i] == 0) {
		ans += s[i];
	}
	return ans;
}

int main () {
	init();
	cout << solve () << endl;
	return 0;
}


Codeforces 383A Milking cows(贪心)

上一篇:Codeforces 384B Multitasking(贪心)


下一篇:拒绝做软件开发的操作工