相关疑难解决方法(0)

我刚刚在UVA的在线评审中遇到了这个小问题,并且认为它可能是一个小代码高尔夫的好候选人.

问题:

您将设计一个程序,以帮助建筑师根据城市中建筑物的位置绘制城市的天际线.为了使问题易于处理,所有建筑物都是矩形的,并且它们共用一个共同的底部(它们内置的城市非常平坦).这个城市也被视为二维的.建筑物由有序三元组(Li,Hi,Ri)指定,其中Li和Ri分别是建筑物i和Hi的左右坐标,是建筑物的高度.

在下图中,建筑物在左侧显示为三元组

(1,11,5), (2,6,7), (3,13,9), (12,7,16), (14,3,25), (19,18,22), (23,13,29), (24,4,28) 

右边显示的天际线由序列表示:

1, 11, 3, 13, 9, 0, 12, 7, 16, 3, 19, 18, 22, 3, 23, 13, 29, 0 

输出应包含描述天际线的矢量,如上例所示.在天际线矢量(v1,v2,v3,... vn)中,i是偶数的vi表示水平线(高度).i是奇数的vi表示垂直线(x坐标).天际线矢量应该表示所采取的"路径",例如,从最小x坐标开始并在定义天际线的所有线上水平和垂直行进的bug.因此,天际线矢量中的最后一个条目将为0.坐标必须用空格分隔.

如果我不计算提供(测试)建筑物的声明并包括所有空格和制表符,我的解决方案在Python中长度为223个字符.

这是精简版:

B=[[1,11,5],[2,6,7],[3,13,9],[12,7,16],[14,3,25],[19,18,22],[23,13,29],[24,4,28]]

# Solution.

R=range
v=[0 for e in R(max([y[2] for y in B])+1)]
for b in B:
   for x in R(b[0], b[2]):
      if b[1]>v[x]:
         v[x]=b[1]
p=1
k=0 …