hiho一下第252周《一面砖墙》题目分析

5
0

这道题猛一看好像没有什么思路,枚举起来感觉挺麻烦的。为了描述方便,我们在水平方向建立一个X轴,X=0的位置设成这面墙的左边缘。X轴的长度单位与砖的长度单位保持一致:

hiho1494x.png

这样对于每一个砖和砖之间交界的缝隙,都有一个X坐标。比如第一层天蓝色的缝隙,X坐标就是6,深蓝色的缝隙坐标就是10;第二层红色的缝隙坐标是8;第三层绿色的缝隙坐标是11。

现在假设我要在X=a这个位置画一条竖线,这条线穿过了多少块砖,显然取决于X=a这个位置有多少个缝隙。这个位置的缝隙越多,穿过的砖数目就越少。

于是我们有了一个比较清楚的枚举算法。首先计算所有砖块交界缝隙的坐标,看哪个坐标的缝隙最多,我们就在哪个坐标画线,这样穿过的砖块肯定最少。我们可以用unordered_map来做,key是缝隙的坐标,value是处于这个坐标的缝隙数量。

0 answer(s)

write answer 切换为英文 切换为中文


转发分享