绿毛的美食

Problem Description

绿毛喜欢美食。
现在有n个美食排成一排摆在绿毛的面前,编号为i(1到n)的食物大小为 a[i] ,即足够绿毛吃 a[i] 口。
绿毛每次会吃两口,这两口要么是同一个的美食,要么是两个相邻的美食。
绿毛想知道,他最多能吃几次?
(1<=n<=1e5,0<=a[i]<=1e9)

Input

第1行一个正整数n,表示美食个数
接下来一行,第i个整数a[i],表示编号为i的美食的大小

Output

一个数表示绿毛最多吃几次。

Sample Input

Sample Output

Hint

用二元组(a,b)表示某一次吃的两个美食分别为第a个美食和第b个美食,则下面为一个吃10次的方案:
(1,2)(2,2)(2,2)(3,4)(3,4)(3,4)(3,4)(3,4)(3,4)(3,4)
注意不一定要吃完。





思路比较清晰

基本原理是贪心思想

由于2要么被前面一个吃一口,要么就自己被吃两口

这两种情况的结果是等价的

并且如果是1的话被前面一个吃效果还是大于被吃两口的

(其他情况由于都可以通过-2转换为这两种情况,所以不予考虑)

所以从前向后模拟

思路是一个数先不断-2,一直到不能减了为止

然后统计次数

再观察后面的一个数是否>=1即能够各自被吃一口

下面贴出代码

注意数据要求一定要long long

因为10^5*2^31是超过int范围的


2019-06-11  00:23:18  Author: WindCry1




0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注