java - TopCoder 最佳选择算法来自 SRM 489 DIV 2(500 分)

Question

我正在查看随机的 TopCoder 问题，以便在比赛中尝试和改进，我今天遇到了一个问题，我希望得到一些意见。

问题陈述

Teddy 喜欢玫瑰，Tracy 喜欢百合。他们希望把这些花种在一个大花园里。

然而，镇上唯一的花店以 vector<int> 代表的小包形式出售这些花。玫瑰和百合。第 i 个数据包包含 roses[i] 玫瑰和 lilies[i] 百合。每包只能购买一次。

Teddy 和 Tracy 想买一些花，把它们摆成一个长方形的格子。这个网格的排列必须使每个单元格只包含一朵花，并且共享一条边的任何两个单元格必须包含不同种类的花。此外，Teddy 和 Tracy 必须使用他们购买的所有鲜花。

Teddy 和 Tracy 喜欢方形网格，所以他们想买一套包装，这样他们就可以将花朵排列成尽可能方形的网格。更准确地说，他们希望将花朵排列成 R x C 网格，其中 R 和 C 是正整数，这样 |R-C| (|R-C|表示R-C的绝对值)被最小化。返回此最小绝对值，如果不存在有效排列，则返回 -1。

定义

类别:BuyingFlowers

方法:buy

参数:vector <int>, vector <int>

返回:int

方法签名:int buy(vector <int> roses, vector <int> lilies)

示例

{2, 4}
{4, 2}

返回:1

买下所有包裹得到 6 朵玫瑰和 6 朵百合，他们可以按照以下排列创建一个 3 x 4 的网格:

RLRL
LRLR
RLRL

这种排列的高宽差为1。

到目前为止我的想法

到目前为止，我对这个问题有一些想法，我认为这些想法可能对解决它很重要。请随意忽略它们。

• 由花朵创建的每个矩形的周边都会有偶数个玫瑰和百合花。所以你可以用花做的最大可能的矩形可以通过取两个数量中较小的一个来找到，比如你有 6 朵玫瑰和 4 朵百合，因为你只有 4 朵百合，你可以做的最大尺寸的矩形将包括 4玫瑰和 4 朵百合花。

• 当您考虑到矩形的每个单元格都必须用一朵花填充时，挑战显然就来了，因此您必须找到“最适合”的矩形，给定您拥有的花的数量，以满足两者:为其余的花朵提供足够的“中间”单元格，并尽可能靠近正方形。

我看过一些已发布的解决方案，但是代码往往非常困惑和优化(就快速编写而言)，因此往往很难提取作者为解决方案考虑的概念.

如果有任何想法，我将不胜感激，我很想了解一些快速解决此类问题的方法。

Answer 1

对于 TopCoder，问题陈述中最重要的部分之一是约束部分，因为这通常规定了在时间限制内什么是可能的，什么不是。

在你的例子中，最多有 16 个数据包。由于可能的子集总数 =2^16=65536 非常少，我们可以查看所有数据包子集并决定哪个产生最佳组合。

为此使用位操作(在 C++ 中)

for(int i=0;i<(1<<16);i++)
{
 //i represents a subset
 for(int j=0;j<16;j++)
   if(i & (1<<j))
   {
    //j-th packet is present in subset
   }
}

给定包的组合后，你能说出你能做出多大的矩形吗？

是的。

提示:当你在左上角固定一朵百合，剩下的花怎么排列？
P.S:只有一种方法。
同样，当你在左上角固定一朵玫瑰时，只有一种方法可以填充矩形。

一旦你选择了这个，只需遍历所有子集的组合，看看哪个产生最小的 |R-C|。

如果您还有其他问题，请询问。