题目链接: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; }