百度“变态比赛规则”算法题 java 的解法

没什么注释。。
作过的看看能不能再快一点
主题贴子在这里。。。。
http://www.iteye.com/post/307049

package com.maodajun.javaeye1;

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class BaiDuQuest {

	public String teamAndImpossable(int peoples,int impossable){
		int maximpossable= maxImpossable(peoples);
		maximpossable -=impossable;
		List list =selfTeam(peoples,maximpossable,new ArrayList());
		if(list!=null){
			return "YES";
		}
		return "NO";	
	}
	//递归算出最大可能。。。循环赛制
	public int maxImpossable(int poples){
		
		if(poples==2){
			return 1;
		}else if(poples<1){
			return 0;
		}
		poples--;
		return maxImpossable(poples)+poples;
	}
	
	public int maxFirstTeam(int peoples, int maximpossable){
		int tmp = 0 ;
		if(maxImpossable(peoples)<maximpossable){
			return -1;
		}
		for(int i = peoples ; i >1 ; i--){
			tmp = maxImpossable(i);
			if(tmp <= maximpossable){
				return i;
			}
		}
		return tmp;
	}
	public List selfTeam(int peoples , int maximpossable ,List list ){
		int max = maxFirstTeam(peoples,maximpossable);
		if(max==0){
			return list;
		}else if (max==-1){
			return null;
		}else{
			list .add(""+max);
			return selfTeam(peoples-max,maximpossable-maxImpossable(max),list);
		}	
	}
	public static  void main(String[] arg){
		BaiDuQuest quest = new BaiDuQuest();
		int people = 5;
		for(int i = quest.maxImpossable(people) ; i >=0; i--){
			List list =quest.selfTeam(people,i,new ArrayList());
			int count = 0 ;
			if(list!=null){
				for(int j = 0 ; j < list.size(); j ++){
					 count +=Integer.parseInt(list.get(j).toString());
					
				}
	
				list.add(""+(people-count));
			}
			System.out.println(quest.maxImpossable(people)-i+":"+list);
		}
	}
	 
	

}

junit :
这东西真是好东西以前要写这么一个东西
想明白到写好至少要调个一两天

package com.maodajun.javaeye1;

import java.util.ArrayList;
import java.util.List;

import junit.framework.TestCase;

/**
 * @author maodajun327
 *
 */
public class BaiDuQuestTest extends TestCase {
	BaiDuQuest quest = null;
	public static void main(String[] args) {
		junit.textui.TestRunner.run(BaiDuQuestTest.class);
	}

	public void setUp(){
		quest =new BaiDuQuest();;
	}

	public void testMaxImpossable(){
		assertEquals(0,quest.maxImpossable(1));
		assertEquals(1,quest.maxImpossable(2));
		assertEquals(3,quest.maxImpossable(3));
		assertEquals(6,quest.maxImpossable(4));
		assertEquals(10,quest.maxImpossable(5));
	}
	public void testListMax(){
		assertEquals(1,quest.maxFirstTeam(4,0));//如果有6－1场赛时第一组1人
		assertEquals(2,quest.maxFirstTeam(4,2));//如果有6－3场赛时第一组2人
		assertEquals(3,quest.maxFirstTeam(4,3));//如果有6－4场赛时第一组3人
		assertEquals(4,quest.maxFirstTeam(4,6));//如果有6－6场赛时第一组为4人
		assertEquals(-1,quest.maxFirstTeam(4,7));//小于0场时第一组为－1人		
	}
	public void testSelfTeam(){

		List list =null;
		list = quest.selfTeam(5,6,new ArrayList());
		assertNotNull(list);
		list = quest.selfTeam(5,7,new ArrayList());
		assertNull(list);
	}
	public void testTeamAndImpossable(){

		 String tmp=null;
		 tmp = quest.teamAndImpossable(5,4);
		assertEquals("YES",tmp);
		tmp = quest.teamAndImpossable(5,5);
		assertEquals("NO",tmp);
	}

}

想法：

10人的话：
最多可以多少场？
1，1，1，1，1，1，1，1，1，1
这样每个人都要与其它人踢。。。
10+9+8+7+6+5+4+3+2+1＝
2，1，1，1，1，1，1，1，1
这样只会少一场。。。就是第一队中的两个人不用互踢
10+9+8+7+6+5+4+3+2=
3,1,1,1,1,1,1,1
以上一次少二场。。。就是有同一队中三个人不用互踢（比上上次要少 2+1场）
10+9+8+7+6+5+4+3＝
3，2，1，1，1，1，1
比上一个少一场
3，3，1，1，1，1
比上一个少二场
。。。。。。。
总场数为：
Sn(总人数)-Sn(第一组人数)－Sn(第二组人数)－Sn(第三组人数)
＝N
等比数列
Sn(总人数)－N＝Sn(team1)+Sn(team2)....
假设
Sn(team1)<Sn(总数)－N<Sn(team1+1)
得出tean1=为所有的组中人数最多的一组
之后
把这组的人数刨去，节省下来的场次数也减去之后
那么就得出一个少了team1人的一个更小的组，重复再找多最大可能的人数。。。。

到，节省不了了为止，如为0则可如为负则不可。。。。

呵呵,我也来写个(DP):

/**
*@author  Eastsun
*@version 1.0 2007/6/9
*/
import java.util.BitSet;
public class BTGame{
    private static final int MAX  = 500;
    private static BitSet isSuit =new BitSet(offset(MAX+1)), isSolved =new BitSet(offset(MAX+1));
    static{
    	for(int k=0;k<=MAX;k++){isSuit.set(offset(k)); isSolved.set(offset(k));}
    }
    private static int offset(int n){  //表示第n个的起始位置
    	  return  n*(n-1)*(n-2)/6 + n;
    }
    public static boolean isSuit(int n,int k){
    	  if(k<0||k>n*(n-1)/2) return false;
    	  int off =offset(n);
    	  if(isSolved.get(off+k)) return isSuit.get(off+k);
    	  for(int i =1;i<n;i++)
    	      if(isSuit(n -i,k -i*(n-i) ) ){
    	      	  isSolved.set(off +k);
    	      	  isSuit.set(off +k);
    	      	  return true;
    	      }
    	  isSolved.set(off +k);
    	  return false;
    }
    
    public static void test(int n,int k){
    	  System.out.println(isSuit(n,k)?"YES":"NO");
    }

    public static void main(String[] args){
        test(2,0);
        test(2,1);
        test(3,1);
        test(3,2);
        test(5,4);
        test(5,5);
    }
    
}

稍微解释下:
BitSet isSolved,isSuit
中的isSolved.get(n,k)表示(n,k)是否已经求解过
isSuit.get(n,k)为true表示n个人可能为k场
简记isSuit.get(n,k)为s[n,k].

n个人能够比k场实际上是问: n能否存在一个分解 xi(xi>0)使得
Sum{xi} =n,  Sum{xi*xj: i!=j} =k;
注意到 Sum{xi}*Sum{xi} = Sum{xi*xj}

                      = Sum{xi*xi} +2 *Sum{xi*xj: i!=j}
又易知   n <=Sum{xi*xi} <= n*n
故可得k的取值范围为:       0<=k <= n*(n-1)/2
因此我们只需判断  k在 [0,n*(n-1)/2]中的取值.



下面我们来推导DP状态转移方程:

假设n存在分解 n = Sum{xi: 1<=i<=L}
使得          k = Sum{xi*xj: 1<=i,j<=L,i!=j}
有:         k = Sum{x1*xi: i!=1} +Sum{xi*xj: 2<=i,j<=L,i!=j}
              = x1*(n-x1) +Sum{xi*xj:2<=i,j<=L,i!=j}
可以看出:     {xi: 2<=i<=L}是 k- x1*(n-x1)的一个满足条件的分解
从而我们有:
        s[n,k] = OR{s[n-m,k-m*(n-m)] : 1<=m<n}
其中OR表示逻辑或运算.


6.11添加:对offset()方法的说明
对于每一个n,我只需计算s[n,0],s[n,1],....,s[n,n*(n-1)/2]
很容易可以想到可以用一个二维boolean数组来保存s的值:
boolean[][] s =new boolean[MAX+1][];       //用MAX+1是因为把n=0的情形也包含进出了
然后:
            s[n] =new boolean[n*(n-1)/2+1]
不过,这里我没有采用boolean数组,而是采用一个BitSet(后面的C代码用的是一个char数组,然后用其每一个bit保存一个值).
BitSet可以看成是一个一维bit数组,但这里我们就要考虑如何将原来的二维boolean数组"拉直"成一维数组了:
显然,我们只要知道s[n]对应的BitSet位置就可以了,这就是offset方法要干的事.
由于s[0]要占1个位,s[1]要占一个位,....,更一般的:
              s[m]的取值是0到m*(m-1)/2
因此,s[m]要占 1+m*(m-1)/2 个位 (呵呵,不要把这个1漏了)
这样,我们可以计算s[n]的在BitSet的偏移位置应该是前s[0],...s[n-1]所占位置的总和,也就是:
     Sum{1+m*(m-1)/2 : 0<=m<=n-1}
唔,这个求和公式比1加到100要难一些(当然,如果你和我一样是学数学的话就不会觉得难了)
总而言之,求和的结果就是:

                       

呵呵,再来个C的:

/**
* BTGame.c
* DP解法
* By Eastsun
*/
#include<stdio.h>
#define OFFSET(n) ((n)*((n)-1)*((n)-2)/6 +(n))
#define GetBit(a,n) (a[(n)>>3]&(1<<((n)&7)))
#define SetBit(a,n) (a[(n)>>3] |=1<<((n)&7))
#define MAX 500
char suit[OFFSET(MAX+1)/8+1],solved[OFFSET(MAX+1)/8+1];
void init(){
	  int k;
	  for(k=0;k<=MAX;k++){SetBit(suit,OFFSET(k)); SetBit(solved,OFFSET(k));}
}
char isSuit(int n,int k){
	 int off =OFFSET(n),i;
	 if(k<0||k>n*(n-1)/2) return 0;
	 if(GetBit(solved,off+k)) return GetBit(suit,off+k);
	 for(i =1;i<n;i++)
	    if(isSuit(n-i,k-i*(n-i))){
	    	  SetBit(solved,off+k);
	    	  SetBit(suit,off+k);
	    	  return 1;
	    }
	  SetBit(solved,off+k);
	  return 0;
}
int main(){
	  int n,k;
	  init();
	  while(scanf("%d%d",&n,&k)!=EOF){
	  	  printf(isSuit(n,k)?"YES\n":"NO\n");
	  }
      return 0;
}

public interface BTQuest {
        //题目需要的方法（作什么用的可以看题）
	public String teamAndImpossable(int peoples,int impossable);
	//算出N人最多可以比多少场
	public int maxImpossable(int poples);
	//算出如果分组的话第一组最多可能有多少人时，减少的场次数小于总数－N
	public int maxFirstTeam(int peoples, int maximpossable);
	//将第一组结果放入list后，由剩下的人组成新的组。。递归运算。。。
	public List selfTeam(int peoples , int maximpossable ,List list );
	}

问了三个人，都说看不懂，加入一个接口与中文解释再看有没有人能看的懂，

实现中的main方法是要打出people=5时所有的可能性。

也把我的解法发上来，思路很简单，按照状态机路径图，从最大分组（全1）到最小分组（一个组）进行遍历追溯，直到找到符合比赛次数的分组方案

此方法效率较低，只是思路简单

分组方案类

package qinysong.arithmetic.btrules;

import java.util.*;

public class Decomposition {

  public static final int maxNumber = 100;

  private int[] groups;  //分组情况，从小到大顺序，格式为0,0,...0,1,...,x1,x2,xn
  private int leftNotZeroIndex;  //最左边不为零的数组索引
  private int matchTime;  //该分组情况下的比赛次数
  
  public Decomposition(int[] groups, int leftNotZeroIndex, int matchTime){
    this.groups = groups;
    this.leftNotZeroIndex = leftNotZeroIndex;
    this.matchTime = matchTime;
  }
  
  /**
   * 取得最大分组，即每组只有一个人的情况
   * @param peopleNumber int
   * @return Decomposition
   */
  public static Decomposition getTheMaxGroup(int peopleNumber){
    int[] groups = new int[maxNumber];
    for (int i = maxNumber - peopleNumber; i < maxNumber; i++){
      groups[i] = 1;
    }
    return new Decomposition(groups,maxNumber - peopleNumber,peopleNumber*(peopleNumber-1)/2);
  }
  
  /**
   * 从groupings分组情况及可导向子分组，比赛次数为checkTime的分组方案
   * @param groupings Set  分组情况集合
   * @param checkTime int  期待比赛次数
   * @return Decomposition  满足比赛次数的分组方案
   */
  public static Decomposition getSuitableGrouping(Set groupings, int checkTime){
    if (groupings.size() == 0) return null;
    Decomposition decomposition = null;
    Set childrenGroups = new HashSet();
    for (Iterator iterator = groupings.iterator(); iterator.hasNext(); ){
      decomposition = (Decomposition) iterator.next();
      if (decomposition.matchTime == checkTime) return decomposition;
      childrenGroups.addAll(decomposition.getUniteChildren(checkTime));
    }
    return getSuitableGrouping(childrenGroups, checkTime);
  }
  
  /**
   * 取得当前分组的可导向子分组
   * 子分组为将当前分组最左边的1，分别加入到后面的分组中
   * 若：当前分组的最左不为零的数大于1，则不必继续求子分组
   * 若：子分组的比赛次数小于checkTime，则舍弃
   * @param checkTime int  设定的比赛次数
   * @return Set
   */
  public Set getUniteChildren(int checkTime){
    Set uniteChildren = new HashSet();
    if (groups[leftNotZeroIndex] > 1) return uniteChildren;
    int unitedMatchTime = 0;
    for (int uniteTo = leftNotZeroIndex + 1; uniteTo < maxNumber; uniteTo++){
      while ((uniteTo != maxNumber-1) && (groups[uniteTo + 1] == groups[uniteTo])){
        uniteTo += 1;
      }
      unitedMatchTime = matchTime - groups[uniteTo];
      if (unitedMatchTime < checkTime ){
        break;
      }
      int[] newGroups = new int[maxNumber];
      System.arraycopy(groups,0,newGroups,0,maxNumber);
      newGroups[uniteTo] += newGroups[leftNotZeroIndex];
      newGroups[leftNotZeroIndex] = 0;
      Decomposition decomposition = new Decomposition(newGroups,leftNotZeroIndex + 1,unitedMatchTime);
      uniteChildren.add(decomposition);
    }
    return uniteChildren;
  }

  public void setGroups(int[] groups) {
    this.groups = groups;
  }
  public void setMatchTime(int matchTime) {
    this.matchTime = matchTime;
  }
  public void setLeftNotZeroIndex(int leftNotZeroIndex) {
    this.leftNotZeroIndex = leftNotZeroIndex;
  }
  public int[] getGroups() {
    return groups;
  }
  public boolean equals(Object decomp2){
    Decomposition decomposition2 = (Decomposition) decomp2;
    return Arrays.equals(groups, decomposition2.groups);
  }
  public int hashCode(){
    return matchTime;
  }
}

测试类

package qinysong.arithmetic.btrules;

import java.util.*;

public class CountCheck {

  public static void main(String[] args) {
    System.out.println("CountCheck.main begin ...");
    int peopleNumber = 20;
    int checkTime = 120;
    Decomposition maxDecomposition = Decomposition.getTheMaxGroup(peopleNumber);
    Set groups = new HashSet();
    groups.add(maxDecomposition);
    Decomposition suitableDecomposition = Decomposition.getSuitableGrouping(groups, checkTime);
    if (suitableDecomposition == null) {
      System.out.println("CountCheck.main 判定结果:" + peopleNumber + "个人不可能产生" + checkTime + "场比赛！");
    } else {
      System.out.println("CountCheck.main 判定结果:" + peopleNumber + "个人可以产生" + checkTime + "场比赛！");
      int[] suitableGrouping = suitableDecomposition.getGroups();
      for (int i = Decomposition.maxNumber-1; suitableGrouping[i] != 0; i--){
        System.out.println(suitableGrouping[i] + "/");
      }
    }
    System.out.println("CountCheck.main begin ...");
  }
}

这个好像错了，自己是不会和自己踢的
1，1，1，1，1，1，1，1，1，1
场数应该是9+8+7+6+5+4+3+2+1＝
......

这个算法就是N个人，最多的时候1个人一组需要
N-1+....+1;
最少时候就是N-1,1
需要N-1组，
具体是，如果有m 个人组成一组，那么就少，m-1+...1 (m>=2)