补墙——单调栈

补墙(wall)
【题目描述】
小R最近在玩一款塔防类游戏。在游戏中，小R修了一排城墙来保护他的基地。在敌人的一轮进攻之后，城墙的许多地方被破坏了，变得参差不齐。小R是一个强迫症患者，他看到这些参差不齐的城墙觉得非常难受，因此决定对这些城墙进行修补。城墙共分为n段，从左到右排成一排，第i段城墙的高度为h_i。相邻两段城墙的高度差距越大，小R看着就越难受，因此他定义整排城墙的混乱程度为相邻两段的高度差之和。需要注意的是，第一段城墙与最后一段城墙都与地面相邻（地面的高度为0）。例如，有一排城墙的高度分别为3,7,2，则这排城墙的混乱程度为3+4+5+2=14。现在小R希望通过使某些段城墙变高的方式降低城墙的总混乱程度，他将一段城墙的高度变高1需要花费1枚金币，现在他希望让总混乱程度小于等于k，请问至少要花费多少金币。


【输入格式】
第一行两个正整数n,k。
第二行n个正整数，第i个正整数表示h_i。


【输出格式】
输出一行一个正整数，表示至少花费的金币。如果无论花费多少金币都无法使得总混乱程度小于等于k，则输出-1。


【输入样例】
5 10
4 2 1 1 3


【输出样例】
2


样例解释
修补后的城墙高度分别为4 2 2 2 3。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！