题目名称	2732. [郑州集训 2017]NOI模拟题1.2
输入输出	`er.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	512 MiB
测试数据	10
题目来源	Arrow 于2017-07-07加入
开放分组	全部用户
提交状态
分类标签	贪心构造
	分享题解

通过：5，提交：8，通过率：62.5%
Kirin	100	0.082 s	3.72 MiB	C++
FoolMike	100	0.132 s	3.74 MiB	C++
再见	100	0.550 s	18.60 MiB	C++
Mr_squre	100	0.595 s	2.60 MiB	C++
Mr_squre	100	0.596 s	2.60 MiB	C++
lyqlyqcogs	10	0.001 s	0.31 MiB	C++
lyqlyqcogs	10	0.001 s	0.31 MiB	C++
lyqlyqcogs	0	0.002 s	0.31 MiB	C++

关于 NOI模拟题1.2 的近10条评论(全部评论)
贪心算法是对的！？考虑倒着做，直接造一颗笛卡尔树，dfs一遍就行了关键是怎么证明贪心的正确性？求神犇证明 FoolMike 2017-07-12 11:31 1楼

2732. [郑州集训 2017]NOI模拟题1.2

★★☆ 输入文件：er.in 输出文件：er.out 简单对比
时间限制：1 s 内存限制：512 MiB

【题目描述】

小火车沉迷垃圾手游不能自拔，他还在玩碧蓝航线。

为了庆祝小火车打捞出了加贺赤城，他决定让你搭建一座纪念塔群，纪念塔共有n 个排成一排，第i 个高度为Hi，也就是由Hi 块砖头组成，你得一块一块砖头搭建。每次你至多能携带k 块砖头，由任意一座塔的底端开始，可以向上移动或者向左右两座塔的同高度移动（前提是那些位置上有砖块），也可以在那些位置摆上砖块（即使是悬空的），并且一旦摆上砖块你就得立刻移动过去。请问你最少需要多少次才能搭建完呢？

【输入格式】

第一行两个整数n,k，表示有n 个纪念塔，每次你可以携带k 块

砖头。

第二行有n 个整数表示Hi。

【输出格式】

一行一个整数表示答案。

【样例输入】

5 10

2 1 2 1 2

【样例输出】

【提示】

对于20%的数据n<=4，Hi<=5；

对于50%的数据满足n<=5000；

对于100%的数据满足n<=100000,0<=Hi<=109,1<=k<=109。