{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv style\u003d\"width:35.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/c7d8baf2d093454f7b7019615646a180?v\u003d1703954082\" alt\u003d\"/problems/scaffolding/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e竹脚手架在香港非常流行。在建筑和建筑物维护中被广泛使用,当需要建造高度临时结构以容纳建筑工人时。你还会在粤剧剧院和长洲的夺旗比赛中看到竹脚手架。\n\n \u003cp\u003e作为一名建筑工人,你想要为即将到来的节日建造一个竹脚手架。对于最终的脚手架有特定的要求,它将成为一个垂直,\u003cspan class\u003d\"tex2jax_process\"\u003e$2$\u003c/span\u003e维的网格的一部分。已经有\u003cspan class\u003d\"tex2jax_process\"\u003e$N+1$\u003c/span\u003e根竹子建立,所以中间有\u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e根竹子。最初所有的竹子都是空的。我们的任务是在第\u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e列中精确地放置\u003cspan class\u003d\"tex2jax_process\"\u003e$H_ i$\u003c/span\u003e根横向短竹子,从下往上。\u003c/p\u003e\n\n \u003cdiv id\u003d\"a0000000004\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/61a3a64f037db7a0244617b057ea9cf5?v\u003d1703954082\" alt\u003d\"\\includegraphics[width\u003d.95\\textwidth ]{diagrams}\" style\u003d\"width:95.00%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003e图1\u003c/b\u003e:左图示意了有\u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e个空列的初始脚手架。右图展示了示例输入2的最终脚手架。\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003cp\u003e你每次最多携带\u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e根短竹子。你将在多个回合中安装短竹子。在每一回合中,你最多携带\u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e根短竹子,并且从地面的任何位置开始。\u003c/p\u003e\n\n \u003cp\u003e你只能站在之前建立的短竹子上(或者在地面上)。然后你有两个选择:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003e如果那里已经有短竹子,你可以向左、右或上爬\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e如果那里还没有短竹子,你可以向左、右或上放置短竹子\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003e请注意,你不能在携带短竹子时往下走。你也不能在自己下方放置短竹子。\u003c/p\u003e\n\n \u003cp\u003e一旦你完成当前回合中所有短竹子的放置,你将回到地面。然后你最多携带\u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e根短竹子,并从地面开始另一轮。这将持续下去,直到你建立了所需的脚手架,在第\u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e列中精确地放置了\u003cspan class\u003d\"tex2jax_process\"\u003e$H_ i$\u003c/span\u003e根短竹子。\u003c/p\u003e\n\n \u003cp\u003e你需要的最少回合数是多少?\u003c/p\u003e\n\n \u003ch2\u003e输入\u003c/h2\u003e\n\n \u003cp\u003e第一行包含两个整数\u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e和\u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e(\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq N \\leq 100\\, 000$\u003c/span\u003e,\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq M \\leq 10^9$\u003c/span\u003e)。第二行包含\u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e个整数\u003cspan class\u003d\"tex2jax_process\"\u003e$H_1, \\dots , H_ N$\u003c/span\u003e(\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq H_ i \\leq 100\\, 000$\u003c/span\u003e)。\u003c/p\u003e\n\n \u003ch2\u003e输出\u003c/h2\u003e\n\n \u003cp\u003e输出一个整数,代表最少的回合数。\u003c/p\u003e\n\n \u003ch2\u003e示例1\u003c/h2\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 4\n2 1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n \u003ch2\u003e示例2\u003c/h2\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 10\n2 1 2 1 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}