除了這個暴力破解方法之外的任何更快的解決方案

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; 
    } 
} 

Answer 2

這裏是我有一個執行用於〜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; 
    } 
}