w*******s 发帖数: 138 | 1 给出若干矩形,矩形可以从大到小重叠摆放,但是放在上面的矩形必须能够完全放入下
面的矩形中,每个矩形上至多只能放另外一个矩形,摆放的时候矩形的边必须相互垂直
或平行(不可任意旋转),求最优摆放方案使得总占地面积最小。
面试应该不会考这么偏的。 |
z***n 发帖数: 11 | 2 这个不就是求最少的路径覆盖所有点,然后转化成二分图匹配 |
w*******s 发帖数: 138 | 3 是占地面积,类似于最少路径,但是有点不一样
【在 z***n 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 这个不就是求最少的路径覆盖所有点,然后转化成二分图匹配
|
l*********u 发帖数: 19053 | 4 先sort矩形长度,由大到小。然后以第一的宽,找下个小的宽的矩形,这是一对。一对
一对找下去。凑不成对的单放。
【在 w*******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 给出若干矩形,矩形可以从大到小重叠摆放,但是放在上面的矩形必须能够完全放入下 : 面的矩形中,每个矩形上至多只能放另外一个矩形,摆放的时候矩形的边必须相互垂直 : 或平行(不可任意旋转),求最优摆放方案使得总占地面积最小。 : 面试应该不会考这么偏的。
|
z****s 发帖数: 409 | 5 楼上什么二分匹配,贪心,完全是扯淡,自己都没仔细想想还好意思发。
想了几个特殊情况,发现这个题还真有点意思,转成DAG之后有点卡住了,感觉要暴力
或者dp了,lz说说数据规模吧。
矩形的长宽范围还有矩形个数的范围都是多少,时限多少? |
w*******s 发帖数: 138 | 6 类似最少路径覆盖,确实是二分匹配和贪心,但是第二个回复是扯淡,是O(n^2)的时间复
杂度和O(n)的空间复杂度
【在 z****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼上什么二分匹配,贪心,完全是扯淡,自己都没仔细想想还好意思发。 : 想了几个特殊情况,发现这个题还真有点意思,转成DAG之后有点卡住了,感觉要暴力 : 或者dp了,lz说说数据规模吧。 : 矩形的长宽范围还有矩形个数的范围都是多少,时限多少?
|
h*****n 发帖数: 15 | |
w*******s 发帖数: 138 | |
b***e 发帖数: 1419 | 9 拓扑排序后产生DAG,然后就是按层数一层一层的进行最大二分匹配。二楼说的是正解
。在自己搞清楚自己是否扯着蛋之前不要随便说别人扯蛋。
【在 z****s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 楼上什么二分匹配,贪心,完全是扯淡,自己都没仔细想想还好意思发。 : 想了几个特殊情况,发现这个题还真有点意思,转成DAG之后有点卡住了,感觉要暴力 : 或者dp了,lz说说数据规模吧。 : 矩形的长宽范围还有矩形个数的范围都是多少,时限多少?
|