jzoj 3822 逆光"/>
jzoj 3822 逆光
Description
Zyh养着n盆太阳花,它们被排在一列直线上。为了简化问题,太阳花的朝向只有向左和向右这两种。Zyh非常喜欢这些花,于是他在每盆花的上方放置了光源。
太阳花和Zyh幸福地生活着,然而每次要关掉这些光源的时候就会出现一个问题。因为Zyh的动作问题,他每次只能关掉一个光源,在关掉这个光源后,这个光源下方的花就会休眠。然而,对于每一个未休眠的太阳花,如果它的朝向向左,那么每看到一个在它左边的光源关闭,它就会认为自己的人生有些黑暗,于是对Zyh的好感减1。同样地,如果它的朝向向右,那么每看到一个在它右边的光源关闭,也会导致它对Zyh的好感减1。
Zyh不想看到太阳花对他的好感下降太多。于是他想知道关掉所有灯后,太阳花下降的好感总值是多少。
Input
输入包含两行。第一行是一个数正整数n表示太阳花的盆数。然后第二行是n个由空格隔开的0或1。0表示向左,1表示向右。
Output
只有一个数,太阳花下降的好感总值。
Sample Input
输入1:
5
0 0 0 1 0
输入2:
5
1 0 1 0 1
Sample Output
输出1:
1
输出2:
3
Data Constraint
对于30%的数据 n<10
对于70%的数据 n<=5000
对于100%的数据 n<=1000000
解题思路
观察数据和尝试可以发现,一定是先关一个方向的灯,在关另一个方向的灯,并且结果一样,所以任选一个方向从其背对的方向开始关,用前缀和维护一下,另一方向就可以无失望的关掉了。
Source Code
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;const int N=1000001;long long a[N],n;int main()
{long long i,t;long long sum=0;scanf("%lld",&n);t=0;for (i=1;i<=n;i++) scanf("%lld",&a[i]);for (i=n;i>=1;i--)if (a[i]==1) {sum=sum+(n-i)-t;t++;}printf("%lld\n",sum);return 0;
}
更多推荐
jzoj 3822 逆光
发布评论