2026-01-18 13:03:53
发布于:江苏
翻译:
题目描述
Iahub 帮助他的祖父在农场干活。今天他必须挤牛奶。有 n 头牛排成一排,从左到右编号为 1 到 n。每头牛都朝左或朝右。当 Iahub 挤一头牛的奶时,所有能看到当前牛的牛都会受到惊吓,并且它们能产出的奶量减少 1 单位。朝左的牛能看到所有编号比她小的牛,朝右的牛能看到所有编号比她大的牛。一头牛可以被惊吓多次(每次再减少 1 单位奶量)。一旦一头牛被挤过奶,它就不会再受到惊吓而减少奶量。可以假设一头牛永远不会失去所有奶量(一头牛能产出无限多的奶)。
Iahub 可以决定挤牛奶的顺序,但他必须每头牛都恰好挤一次。Iahub 希望尽可能少地损失奶量。请输出最少损失的奶量。
输入格式
第一行包含一个整数 n(1 <= n <= 200000)。第二行包含 n 个整数 a1, a2, ..., an,其中 ai 是 0 表示第 i 头牛朝左,是 1 表示朝右。
输出格式
输出一个整数,即最少损失的奶量。
请注意,在 C++ 中,不要使用 %lld 标志符来读取或写入 64 位整数。建议使用 cin、cout 流或 %I64d 标志符。
输入输出样例
输入#1
4
0 0 1 0
输出#1
1
输入#2
5
1 0 1 0 1
输出#2
3
说明/提示
在第一个样例中,Iahub 按以下顺序挤牛奶:牛 3,牛 4,牛 2,牛 1。当他挤牛 3 时,牛 4 损失 1 单位奶量。之后没有更多的奶损失。
这里空空如也















有帮助,赞一个