Vittorio想搭建一个模型,其中一些紫色积木块在如下n个位置:(x1,0,h),(x2,0,h),...,(xn,0,h)—这 些位置是积木块底面中心的坐标,注意这些积木块所有的y=0且z=h。 Vittorio将用其他颜色的积木块来支撑紫色积木块,他希望放置积木块的位置满足底面中心坐标y=0。 搭建一个有效的模型。 输入: – 第一行包括两个整数n和h(1≤n≤300,0≤h≤109), 分别为紫色积木块数和对应的z坐标值。 – 第二行包括n个整数x1,x2,...,xn(1≤xi≤109, xi+1<xi+1),分别为紫色积木块的x坐标值且按递 增排序。 u 输出: – 输出搭建有效模型所需最少的附加积木块数目。
时间: 2023-05-25 12:03:45 浏览: 50
思路:对于每个紫色积木块,找到其左边最靠近的一个紫色积木块和右边最靠近的一个紫色积木块,这两个紫色积木块连成一条边,每条边上需要填充积木块的个数即为左右两个紫色积木块之间的距离减一,求所有边需要填充的积木块数之和即为所求。
注意要特判边缘情况,即左边没有紫色积木块和右边没有紫色积木块的情况。
时间复杂度:$O(n)$
C++ 代码