CF383A Milking cows

    • 316通过
    • 605提交
  • 题目来源 CodeForces 383A
  • 评测方式 RemoteJudge
  • 标签 前缀和 概率论,统计 贪心
  • 难度 省选/NOI-
  • 时空限制 1000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    题目描述 Iahub在农场帮助他的祖父,今天他必须挤牛奶。农场里有$n$只牛左成一排,从左到右编号$1$到$n$。每只牛不是面向左边就是面向右边。当Iahub挤某一只牛的牛奶时,所有看得到这当前只牛的牛都会因为受到惊吓而损失一单位量的牛奶。面向左边的牛可以看到它左边的所有牛(不包括自己),面向右边的牛可以看到它右边的所有牛(不包括自己)。被惊吓过的牛可以再次被惊吓。被挤过奶的牛不会再被惊吓。我们假定每一头牛可以生产无限量的牛奶。

    Iahub可以决定挤牛奶的顺序,但他必须每头牛都要挤。Iahub想损失尽可能少的牛奶。请输出最少的牛奶损失量。

    输入输出格式

    输入格式 第一行包括一个整数$n(1<=n<=200000)$. 第二行包括n个整数$a_1,a_2...,a_n$。$a_i$是$0$表示牛面向左边,$1$则表示面向右边。

    输出格式 输出一个整数,即最少的牛奶损失量

    在C++中,请不要用%lld分类符来读入或输出64位整型。最好用输出输出流或者%I64D分类符

    说明 在第一个样例中,Iahub按照下面的顺序可以使得牛奶损失最少:$3,4,2,1$。当他挤牛$3$时,牛$4$会损失$1$单位牛奶。在此之后,没有牛奶损失。

    Translated by @Imakf

    题目描述

    Iahub helps his grandfather at the farm. Today he must milk the cows. There are $ n $ cows sitting in a row, numbered from $ 1 $ to $ n $ from left to right. Each cow is either facing to the left or facing to the right. When Iahub milks a cow, all the cows that see the current cow get scared and lose one unit of the quantity of milk that they can give. A cow facing left sees all the cows with lower indices than her index, and a cow facing right sees all the cows with higher indices than her index. A cow that got scared once can get scared again (and lose one more unit of milk). A cow that has been milked once cannot get scared and lose any more milk. You can assume that a cow never loses all the milk she can give (a cow gives an infinitely amount of milk).

    Iahub can decide the order in which he milks the cows. But he must milk each cow exactly once. Iahub wants to lose as little milk as possible. Print the minimum amount of milk that is lost.

    输入输出格式

    输入格式:

    The first line contains an integer $ n $ $ (1<=n<=200000) $ . The second line contains $ n $ integers $ a_{1} $ , $ a_{2} $ , ..., $ a_{n} $ , where $ a_{i} $ is $ 0 $ if the cow number $ i $ is facing left, and $ 1 $ if it is facing right.

    输出格式:

    Print a single integer, the minimum amount of lost milk.

    Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

    输入输出样例

    输入样例#1: 复制
    4
    0 0 1 0
    
    输出样例#1: 复制
    1
    输入样例#2: 复制
    5
    1 0 1 0 1
    
    输出样例#2: 复制
    3

    说明

    In the first sample Iahub milks the cows in the following order: cow $ 3 $ , cow $ 4 $ , cow $ 2 $ , cow $ 1 $ . When he milks cow $ 3 $ , cow $ 4 $ loses $ 1 $ unit of milk. After that, no more milk is lost.

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。