1

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

问题陈述 

泰迪喜欢玫瑰，特蕾西喜欢百合花。他们希望将这些花种在一个大花园里。

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

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

泰迪和特蕾西喜欢方形网格，所以他们想买一套小包，这样他们就可以把花排列成最方形的网格。更准确地说，他们希望将花朵排列成 R x C 网格，其中 R 和 C 是正整数，使得 |RC| （|RC| 表示 RC 的绝对值）被最小化。返回此最小绝对值，如果不存在有效排列，则返回 -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。

到目前为止我的想法

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

  • 由花朵创建的每个矩形的周边都会有偶数朵玫瑰和百合花。所以你可以用花做的最大矩形可以通过取两者中较小的一个来找到玫瑰和 4 朵百合花。

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

我查看了一些发布的解决方案，但是代码往往非常模糊和优化（就快速编写而言），因此很难提取作者为解决方案考虑的概念。

我会很感激任何想法，我很想了解一些快速解决此类问题的方法。

4

3 回答 3

0

考虑以下问题：在矩阵 N * M 中，我可以放置超过一半的矩阵百合/玫瑰吗？

回答这个问题应该可以让你完成这个问题。

于 2013-08-30T01:22:16.617 回答
0

查看http://community.topcoder.com/stat?c=problem_statement&pm=11191的示例，看起来只有两种可能性：

|number of roses - number of lillies| == 1, for odd R and odd C

or

number of roses == number of lillies, for even R or even C

如果这是真的，我会寻找一种方法来找到可以划分为最接近的两个整数因子（理想情况下是平方根）的数字lillies + roses（其中num lillies == num roses或）。|num roses - num lillies| == 1

在 TopCoder 示例中，我们有：

Example 0:     6 + 6 = 12, closest two factors 3x4
Example 1:     5 + 4 = 9, closest two factors 3x3

JavaScript 示例：

function closestFactors(n)
{
    var start = Math.floor(Math.sqrt(n))
    while (n % start != 0)
        start--
    return [start,n / start]
}

var roses = [1, 208, 19, 0, 3, 234, 1, 106, 99, 17],
    lillies = [58, 30, 3, 5, 0, 997, 9, 615, 77, 5]

function f(index, currentR, currentL, best)
{ 
    if (roses.length == index)
        return best
    for (var i = index; i < roses.length; i++) 
    {
        var cr = currentR + roses[i],
            cl = currentL + lillies[i]
        if (cr == cl || Math.abs(cr - cl) == 1)
        {
            var cf = closestFactors(cr + cl),
                current = Math.abs(cf[0] - cf[1])
            if (current == 0)
                return 0
            best = best < 0 ? current : Math.min(best,current)
        }
        best = best < 0 ? f(i + 1, cr, cl, best)
                        : Math.min(best,f(i + 1, cr, cl, best))
        if (best == 0)
            return 0
    }
    return best
}

控制台输出：

f(0,0,0,-1)
36
于 2013-08-30T03:18:49.903 回答
0

对于 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
   }
}

一旦你得到一组数据包，你能说出你能做出多大的矩形吗？

是的。

提示：当你在左上角固定一朵百合花时，你如何安排剩余的花朵？
PS：只有一种方式。
同样，当您在左上角固定一朵玫瑰时，只有一种方法可以填充矩形。

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

请询问您是否有更多问题。

于 2013-08-30T03:24:28.753 回答