3

今天，我参加了 google Code Jam 第 1B 轮。在代码堵塞中，有一个名为“Osmos”的问题：https ://code.google.com/codejam/contest/2434486/dashboard

问题描述

问题是有一个游戏，玩家是一个东西，只能吃比它小的东西，并且会随着他吃的东西的大小而变大。例如，如果玩家的尺码为 10 并且吃了 8 码的东西，它就会变成 18 码。

现在，考虑到玩家开始时的大小以及游戏中所有其他事物的大小，您应该给出使游戏可击败所需的最少操作数，这意味着您最终可以吃掉所有东西。

一个操作可以是添加一些东西，也可以是删除一些东西。

我使用的代码

write_case是一个函数，它以正确的格式为每个测试用例编写输出。我在其他代码堵塞回合中使用过它，我知道它是正确的，并且inp是输入文件的文件对象。

cases = int(inp.readline())
for case in xrange(cases):
    # armin is the variable containing the size of the player,
    armin, n = int(inp.readline.split()[0])
    # others is a list of sizes of other things
    others = [int(x) for x in inp.readline().split()]

    # changes obviously holds the number of required changes
    changes = 0
    for other in sorted(others):  #we loop over all the other things in order.
        if other < armin:  #if the other thing is smaller, eat it, no change needed.
            armin += other
        else: # we'll need to make some changes
            # adding is the biggest size thing the player can eat,
            adding = armin - 1
            if other < armin + adding:  #if adding such a thing is good enough
                                        # to eat the other thing
                armin += adding + other # add it and eat them
                changes += 1 #we've made a change.
            else: # we can't add a big enough thing
                # we have to elete it from the game (skip it from the loop)
                # which is a change 
                changes += 1

    write_case(case + 1, changes ) #output the changes.

我背后的逻辑

通过循环从小到大的其他东西，玩家首先会吃掉它通常可以吃的所有东西。当我们遇到不能吃的东西时，我们已经吃掉了比它小的东西，所以我们必须添加一个新的东西，这样我们才能成长。如果我们要添加新的东西，我们不妨让它尽可能大，因为我们添加的东西的大小不会改变操作的数量。我可以添加的最大可食用的东西是播放器的尺寸 -1。如果这足以吃下一个东西，我们添加它，吃我们添加的东西，然后吃我们以前不能吃的东西。

如果添加还不够，我们不添加它，而只是删除（忽略）当前事物）。在这一点上，我可以从循环中跳出跳过所有其他的东西（因为它们都太大而不能吃，所以列表是排序的。），但是将它们的数量添加到操作数中以加快我的解决方案，但这不会改变结果。

此代码正确计算示例输入的值，但对于比赛输入不正确。知道为什么吗？

4

3 回答 3

2

我的方法是，每次找到一个块时，我都会计算出需要添加多少才能继续。然后我建立了一个添加数量和剩余数量的日志。完成设置后，我反向循环浏览日志，以确定添加节点以继续，还是删除每个块点的剩余节点是否更有效。现在看这个，我可以看到许多可以优化的地方，但是我通过下面的 C# 代码通过了小型和大型。

protected string Solve(string Line1, string Line2)
{
    string[] Inputs = Line1.Split();
    uint A = uint.Parse(Inputs[0]);
    byte N = byte.Parse(Inputs[1]);
    Inputs = Line2.Split();
    List<uint> Motes = new List<uint>(N);
    foreach (string Size in Inputs)
    {
        Motes.Add(uint.Parse(Size));
    }
    Motes.Sort();
    List<Action> Actions = new List<Action>();

    while (Motes.Count > 0)
    {
        if (A > Motes[0])
        {
            A += Motes[0];
            Motes.RemoveAt(0);
        }
        else if(A > 1)
        {
            uint I;
            for (I = 0; A <= Motes[0]; I++)
            {
                A = (A << 1) - 1;
            }
            Actions.Add(new Action(I, Motes.Count));
        }
        else
        {
            Actions.Add(new Action(101, Motes.Count));
            break;
        }
    }

    uint TotalInserts = 0;
    int TotalRemoved = 0;
    for (int I = Actions.Count - 1; I >= 0; I--)
    {
        int StepRemaining = Actions[I].Remaining - TotalRemoved;
        uint StepInsert = Actions[I].Inserts;
        if (StepInsert >= StepRemaining)
        {
            TotalRemoved += StepRemaining;
            TotalInserts = 0;
        }
        else
        {
            TotalInserts += StepInsert;
            if (TotalInserts >= Actions[I].Remaining)
            {
                TotalRemoved = Actions[I].Remaining;
                TotalInserts = 0;
            }
        }
    }

    return (TotalInserts + TotalRemoved).ToString();
}
struct Action
{
    public uint Inserts;
    public int Remaining;
    public Action(uint inserts, int remaining)
    {
        Inserts = inserts;
        Remaining = remaining;
    }
}
于 2013-05-05T19:08:38.667 回答
1

以下是我认为的关键点：

  1. 从列表的中心移除是永远不可取的。那是浪费的操作。考虑一下armin, others == 2, [1, 10, 11]- 删除1011 永远不会使 11 更容易到达
  2. 鉴于此，仅删除列表中的所有剩余项目才有效。因此，如果您必须添加比列表中剩余的项目更多的项目才能前进到下一个元素，那么删除那些大的项目会更有效。

我的正确解决方案实施为：

def solve(armin_size, sizes):
    sizes = sorted(sizes)
    steps = 0

    for i, size in enumerate(sizes):
        add_count = 0
        remove_count = len(sizes) - i
        while armin_size <= size:
            armin_size += armin_size - 1
            add_count += 1

            if add_count >= remove_count:
                return steps + remove_count

        armin_size += size
        steps += add_count

    return steps

编辑：刚刚再次检查了记分牌 - 我弄错了。哎呀。

于 2013-05-04T22:39:25.173 回答
1

所以你的问题看起来像如果加法不够好会发生什么......因为你可以在此之后引入另一个微粒来继续喂你的，直到它足够大。如果你不打算再喂它一个微尘，你不妨说你要删除所有剩余的微尘。

如果您有兴趣，我在这里发表了一个很好的关于这个问题的描述。

于 2013-05-05T22:47:42.713 回答