这是我在 ~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;
}
}