Milking cows

wjh15101051's space

卧薪尝胆，厚积薄发。

Milking cows

Date: Fri Nov 02 17:19:18 CST 2018

In Category: NoCategory

Description：

有一排奶牛，分别向左和向右看，如果某只奶牛还没有被挤过奶，并且看到它看的方向一只奶牛被挤奶了，他就会被惊吓，按一个顺序挤奶，最小化被惊吓的次数和。

$1\leqslant n\leqslant 2\times 10^5$

Solution：

如果两只奶牛左边的向右看，右边的向左看，那么一定会产生一次惊吓，而如果不是上述情况，一定有一种方法不产生一次惊吓，于是答案就是这样的对数，直接统计一下就好了。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R char c = getchar();

	while(c != '0' && c != '1')c = getchar();

	return c - '0';

}

int n;

#define MAXN 200010

int a[MAXN];

int main()

{

	scanf("%d",&n);

	int sum = 0;

	long long ans = 0;

	for(int i = 1;i <= n;++i)

	{

		a[i] = rd();

		ans += sum * (a[i] ^ 1);

		sum += a[i];

	}

	cout << ans << endl;

	return 0;

}

In tag: 算法-贪心

wjh15101051