除此蛮力方法外的任何更快解决方案

Question

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

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

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

我的Java代码是迄今为止最快的解决方案排名

非常感谢！

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

以下是在~0.00013秒内（在我的CPU上）执行样本测试的结果：

import java.io.*; 
import java.util.List;
import java.util.ArrayList; 
import java.util.Map;
import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Arrays;

/**
 * Hero.java
 *
 * This program solves the Super Hero problem put forth by Timus Online Judge  
 * http://acm.timus.ru/problem.aspx?space=1&num=1922
 *
 * @author  Hunter McMillen
 * @version 1.0 12/29/2012
 */
public class Hero {
    private static Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
    private static List<Integer>                indices  = new ArrayList<Integer>();
    private static boolean[]                    used;

    /**
     * Entry point into the application
     *
     * @args command line arguments
     */ 
    public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    int numHeroes, wish;
    List<Integer> heroes = new ArrayList<Integer>();
    List<List<Integer>> groups;

    // read number of heroes 
    numHeroes = Integer.parseInt(in.readLine());

    // read 'numHeroes' wishes from stdin
    // filter out heroes that have a minimum required that exceeds
    // the number of heroes
    for(int i = 0; i < numHeroes; i++) {
        wish = Integer.parseInt(in.readLine());
        if(wish <= numHeroes)
        heroes.add(wish);
    }

    // split into groups
    groups = reliableGroups(heroes);

    // output results
    System.out.println(groups.size());
    for(List<Integer> g : groups) {
        System.out.println(g.size() + " " + g.toString().replaceAll("[\\]\\[\\,]", ""));
    }
    }

    /**
     * Determines whether a group is effective, meaning that all wishes
     * for that group are met
     *
     * @group The group to evaluate for effectiveness
     */
    public static boolean isEffective(List<Integer> group)  {
    int maxWish = Integer.MIN_VALUE;
    int temp; 

    // find the maximum wish size of all members in group
    for(int i = 0; i < group.size(); i++) {
        if((temp = indexMap.get(group.get(i))) > maxWish)
        maxWish = temp;
    }

    // make sure that the maximum wish size is respected
    return group.size() >= maxWish;
    }

    /**
     * Checks to see if there exists some other superhero
     * that when added to this group makes another effective group
     *
     * @effectiveGroup The current grouping that is effective but might
     *                 not be reliable
     */ 
    public static boolean isReliable(List<Integer> effectiveGroup) {
    for(int i = 1; i <= indices.size(); i++) {
        if(!used[i]) {
        // add another hero to this group to see if it remains effective 
        effectiveGroup.add(i);

        // if it is still effective, then this group is not reliable
        if(isEffective(effectiveGroup))
            return false;

        // remove the hero that was temporarily added
        effectiveGroup.remove(effectiveGroup.size()-1);
        }
    }

    // true if adding any unused member to this group made it ineffective
    return true;
    }

    /**
     * Separates the List<Integer> of heroes into reliable groups
     *
     * @heroes The List of heroes
     */
    public static List<List<Integer>> reliableGroups(List<Integer> heroes) {
    List<List<Integer>> groups = new ArrayList<List<Integer>>();
    boolean       effective    = true;
    int h, current;

    // create HashMap with mapping between hero wish values and their index
    for(int i = 1; i <= heroes.size(); i++) {
        indices.add(i);
        indexMap.put(i, heroes.get(i-1));
    }

    // create an array to track which heroes have been used
    used = new boolean[indices.size()+1];
    Arrays.fill(used, false);

    List<int[]>   combinations;
    List<Integer> tempList;
    for(int i = 1; i <= indices.size(); i++) { 
        h = indexMap.get(i);

        combinations = combination(heroes, h);

        // iterate over all combinations making sure the wish values are below
        // the threshold for this hero at map index `i`
        for(int[] aCombination : combinations) {
        for(int j = 0; j < aCombination.length; j++) {
            current = aCombination[j];
            used[current] = true;
            if(indexMap.get(current) > h) {
            effective = false;
            break;
            }
        }

        // create a List from the integer[] combination
        tempList = asList(aCombination);

        // if the group makeup is reliable, save it
        if(effective && !groups.contains(tempList) && isReliable(tempList))
            groups.add(new ArrayList<Integer>(tempList));

        // reset flags
        effective = true;
        Arrays.fill(used, false);
        }
    }

    return groups;
    }

    /**
     * Helper method that returns a List<Integer> given  
     * an array of primitive ints
     *
     * @array The array to convert to a List<Integer>
     */
    public static List<Integer> asList(int[] array) {
    List<Integer> boxed = new ArrayList<Integer>();

    for(int i = 0; i < array.length; i++) {
        boxed.add(array[i]);
    }

    return boxed;
    }

    /**
     * Generates the intial r combination in ascending order
     * i.e [1, 2, 3, 4, ..., r]
     *
     * @r The size of the intial combination
     */ 
    public static int[] initialCombination(int r) {
    int[] indices = new int[r];

    for(int i = 0; i < r; i++)
        indices[i] = i+1;

    return indices;
    }

    /**
     * Generates the next combination given an array of indices
     * 
     * @indicesIn The array of indices
     * @n         The size of this combination
     */
    public static int[] nextCombination(int[] indicesIn, int n) {
    int[] indices = (int[])indicesIn.clone();
    int r = indices.length;

    // find the rightmost index that is not at its final highest value
    int i = 0;
    for (i = r - 1; i >= 0; i--) {
        if (indices[i] != (i + n - r + 1)) {
        break;
        }
    }

    // return null if no more combinations exist
    if (i == -1)
        return null;

    // increment rightmost index
    indices[i]++;

    // reset all the indices to the right of indices[i]
    // to their smallest possible value.
    for (int j = i + 1; j < r; j++) {
        indices[j] = indices[j-1] + 1;
    }

    return indices;
    }

    /**
     * Generates all r-combinations of the indices array
     * 
     * @heroes The array of heroes wishes
     * @r      The length of the combination to generate
     */
    public static List<int[]> combination(List<Integer> heroes, int r) {
    List<int[]> combinations = new ArrayList<int[]>();
    int[] indices = initialCombination(r);

    while(indices != null) {
        combinations.add(indices);
        indices = nextCombination(indices, heroes.size());
    }

    return combinations;
    }
}

Answer 2

首先，我的结果（Java）是最快的。http://acm.timus.ru/rating.aspx?space=1

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

因此，主循环只需改为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;
    }
}