小明的喷涂计划——高级

 3 Sec 64 MB |  显示标签
711
通过提交

题目描述

小明有一段破旧的围栏要喷涂。围栏由N个木板构成,每个宽度都为1cm,但是高度各不相同。这个任务非常简单,他给自己买了一个喷漆机器,喷涂头有Xcm宽。
小明的喷漆机器是直接喷射的,因此喷头的每一个部位必须一直接触到木板,否则尤其会污染他的农田。并且机器也必须时刻与地面平行。可以看出,小明必须同时对X个木板同时喷涂,且从底部到达最短的那个木板。然后再选择连续的X个……
由于机器的特殊性,有可能有部分木板没有被喷涂。小明希望这样的木板面积最少,并且喷涂的次数尽量的少。

输入格式

第一行两个整数N(1<=N<=1,000,000),表示木板个数,以及X(1<=X<=100,000)表示碰头宽度。喷头宽度不会超过围栏的宽度。
第二行N个正整数,表示每个木板的高度,并且都不超过1,000,000。

输出格式

最少的未喷涂面积,以及最少的喷涂次数。

样例输入 #1

5 3
5 3 4 4 5


10 3
3 3 3 3 3 3 3 3 3 3


7 4
1 2 3 4 3 2 1


样例输出 #1

3
2


0
4


4
4

 上传者
coach
 创建时间
2012-11-13 12:22