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