java - 除了这种蛮力方法之外的任何更快的解决方案

Question

我一直在 ACM 提交程序来解决这个问题。 Problem ID=1922但我的解决方案在测试 3 中一直超出时间限制。

我的想法是使用蛮力但有一些分支切断。下面是我的 Java 代码，任何更快的解决方案或改进将不胜感激......我想这一点也不难，因为难度只有 195，但我就是无法接受它。

终于接受了。该算法是先对英雄进行排序，从最小的愿望开始。只是 O(n)..

我的 Java 代码是迄今为止最快的 Solution Rank

非常感谢!

public class testtest
{
    static boolean[] used;
    // length of heros
    static int ulen;
    // list of heros
    static Wish[] w;
    // number of possible teams
    static int count = 0;
    // and output
    static StringBuilder str = new StringBuilder();

    // add the team

    // check if it is a valid team
    static boolean check(int len)
    {
        for (int i = 0; i < ulen; i ++)
        {
            if (!used[i])
            {
                            // adding another hero makes it reliable, so invalid
                if (w[i].wish <= len + 1)
                {
                    return false;
                }
            }

        }
        return true;
    }

    // search the teams, team size = total, current pick = len, start from root + 1
    static void search(int root, int total, int len)
    {
        if (len >= total) // finish picking len heros
        {
            if (check(total))  // valid
            {
                print(total);  // add to output
            }
            return;
        }
        for (int i = root + 1; i < ulen; i ++)
        {
            if (w[i].wish > len + ulen - i)
            {
                return; // no enough heros left, so return
            }
            else
            if (w[i].wish <= total)  // valid hero for this team
            {
                used[i] = true;
                search(i, total, len + 1);  // search next hero
                used[i] = false;
            }
        }
    }

    public static void main(String[] args) throws IOException
    {
        BufferedReader rr = new BufferedReader(new InputStreamReader(System.in));
        ulen = Integer.parseInt(rr.readLine());
        w = new Wish[ulen];
        for (int i = 0; i < ulen; i ++)
        {
            w[i] = new Wish(i + 1, Integer.parseInt(rr.readLine()));
        }
        Arrays.sort(w);
        used = new boolean[ulen];
        Arrays.fill(used, false);
        for (int i = 1; i <= ulen; i ++)
        {
            for (int j = 0; j <= ulen - i; j ++)
            {
                if (w[j].wish <= i) // this hero is valid
                {
                    used[j] = true;
                    search(j, i, 1);
                    used[j] = false;
                }
            }
        }
        System.out.println(count);
        System.out.print(str);
    }
}

Answer 1

首先，我的(Java)结果是最快的。 http://acm.timus.ru/rating.aspx?space=1&num=1922&lang=java

我之前没有充分利用的是，我已经按照他们的意愿对英雄列表进行了排序。

因此，主循环只需要改为O(n)而不是O(n^2)

for (int i = 1; i <= ulen; i ++)
{
    if (w[0].wish <= i)
    {
        used[0] = true;
        search(0, i, 1);
        used[0] = false;
    }
}