19~Blog | 今天总是好过昨天~

package com.ll19.test.subject;
import java.util.ArrayList;
public class S1 {
	/**
	 * 有一种体育竞赛共含M个项目， 有运动员A，B，C参加， 在每一项目中， 第一,第二,第三名分别的X，Y，Z分， 其中X,Y,Z
	 * 为正整数且X>Y>Z。 最后A得22分，B与C均得9分，B在百米赛中取得第一。求M的值，并问在跳高中谁得第二名。
	 * 
	 * @author <a href="http://www.LL19.com/">LL19.com</a>
	 */
 
	// m个项目 起码有两个或以上的项目
	private int m = 0;
 
	// abc三人可能名次的全部组合
	private static ArrayList<string> rankList = new ArrayList</string><string>();
 
	// m个项目所有可能的名次组合
	private static ArrayList</string><string> pRankList = new ArrayList</string><string>();
 
	// 所有可能的一二三名分数组合（起码有两个或以上的项目 、B得过第一、X小于等于8(9-1) 大于等于3）
	private static ArrayList</string><string> pointList = new ArrayList</string><string>();
 
	// 运动员a b c
	private String a = "a";
	private String b = "b";
	private String c = "c";
 
	// 最后得分
	private int aPoint = 22;
	private int bPoint = 9, cPoint = 9;
 
	public static void main(String[] args) {
		// PS：命名S1时并未想到曰本著名会社
		long begin = System.currentTimeMillis();
		S1 s1 = new S1();
		s1.loop();
		System.out.println("执行时间:" + (System.currentTimeMillis() - begin)
				+ "毫秒");
	}
 
	/**
	 * 
	 * 得到abc三人可能名次的全部组合
	 */
	public S1() {
		// abc三人可能名次的全部组合
		ArrayList</string><string> personList = new ArrayList</string><string>();
		personList.add(a);
		personList.add(b);
		personList.add(c);
		combination(new StringBuffer(""), personList, personList.size(), false,
				rankList, "");
		// System.out.println(rankList);
		// 可能的一二三名分数组合
		// B得过第一、X起码小于等于8(9-1)
		ArrayList</string><string> tmpPointList = new ArrayList</string><string>();
		tmpPointList.add("8");
		tmpPointList.add("7");
		tmpPointList.add("6");
		tmpPointList.add("5");
		tmpPointList.add("4");
		tmpPointList.add("3");
		tmpPointList.add("2");
		tmpPointList.add("1");
		combination(new StringBuffer(""), tmpPointList, 3, false, pointList, "");
		filterPointList();
		checkPoint();
		// System.out.println(pointList);
	}
 
	/**
	 * 循环
	 */
	public void loop() {
		// 几个随意的遍历的条件(没有仔细揣摩 = =):
		// M起码有两个或以上的项目
		// ABC三人总分40
		// B得过第一、B的总分为9、X起码小于等于8(9-1)
		// X>Y>Z x大于等于3 前三名最少分数是 3+2+1=6
		// 则M最大为6（根据总分40和前三名最小分数和6得到）
		for (int i = 2; i < = 6; i++) {
			m = i;
			// 过滤M m(x+y+z) = 40 为了减少循环次数
			if (checkM()) {
				// System.out.println(m);
				pRankList.clear();
				combination(new StringBuffer(""), rankList, m, true, pRankList,
						";");
				checkB();
				// System.out.println(pRankList);
				for (int j = 0; j < pRankList.size(); j++) {
					for (int k = 0; k < pointList.size(); k++) {
						if (points(pointList.get(k)) * m == 40) {
							if (checkABC(pRankList.get(j), pointList.get(k))) {
								System.out.println("项目数：" + m);
								System.out.println("名次：" + pRankList.get(j));
								System.out.println("每个项目的分数："
										+ pointList.get(k));
							}
						}
					}
				}
			}
		}
	}
 
	/**
	 * 最后A得22分，B与C均得9分
	 */
	private boolean checkABC(String rank, String point) {
		String ranks[] = rank.split(";");
		char xyz[] = point.toCharArray();
		int counta = 0;
		int countb = 0;
		int countc = 0;
		for (int i = 0; i < ranks.length; i++) {
			char abc[] = ranks[i].toCharArray();
			for (int j = 0; j < abc.length; j++) {
				if (String.valueOf(abc[j]).equals("a")) {
					counta += Integer.valueOf(String.valueOf(xyz[j]));
				} else if (String.valueOf(abc[j]).equals("b")) {
					countb += Integer.valueOf(String.valueOf(xyz[j]));
				} else if (String.valueOf(abc[j]).equals("c")) {
					countc += Integer.valueOf(String.valueOf(xyz[j]));
				}
			}
		}
		if (counta == aPoint && countb == bPoint && countc == cPoint) {
			return true;
		} else {
			return false;
		}
	}
 
	/**
	 * 过滤M m(x+y+z) = 40 和分数队列的所有匹配 返回可能的符合条件
	 */
	private boolean checkM() {
		boolean b = false;
		for (int i = 0; i < pointList.size(); i++) {
			// 40分判断
			String point = pointList.get(i);
			int count = points(point);
			if (m * count == 40) {
				b = true;
				break;
			}
		}
		return b;
	}
 
	/**
	 * B得过第一
	 */
	private void checkB() {
		ArrayList<String> tmp = new ArrayList</string><string>();
		for (int j = 0; j < pRankList.size(); j++) {
			String ranks[] = pRankList.get(j).split(";");
			boolean b = false;
			for (int i = 0; i < ranks.length; i++) {
				if (ranks[i].startsWith("b")) {
					b = true;
				}
			}
			if (b) {
				tmp.add(pRankList.get(j));
			}
		}
		pRankList = tmp;
	}
 
	/**
	 * 对分数队列进行过滤 删除不符合条件的分数组合
	 * 
	 * X>Y>Z x大于等于3
	 */
	private void filterPointList() {
		ArrayList</string><string> tmpList = new ArrayList</string><string>();
		for (int i = 0; i < pointList.size(); i++) {
			int pX = Integer.valueOf(String.valueOf((pointList.get(i)
					.toCharArray()[0])));
			int pY = Integer.valueOf(String.valueOf((pointList.get(i)
					.toCharArray()[1])));
			int pZ = Integer.valueOf(String.valueOf((pointList.get(i)
					.toCharArray()[2])));
			if (pX < 3 || pZ > pY || pZ > pX || pY > pX) {
 
			} else {
				tmpList.add(pointList.get(i));
			}
		}
		pointList = tmpList;
	}
 
	/**
	 * ABC三人总分40 分数加起来应该能被40整除
	 */
	private void checkPoint() {
		ArrayList</string><string> tmp = new ArrayList</string><string>();
		for (int i = 0; i < pointList.size(); i++) {
			// 40分判断
			String point = pointList.get(i);
			int count = points(point);
			if (40 % count == 0) {
				tmp.add(pointList.get(i));
			} else {
			}
		}
		pointList = tmp;
	}
 
	/**
	 * 
	 * 求和
	 */
	private int points(String point) {
		char[] c = point.toCharArray();
		int count = 0;
		for (int j = 0; j < c.length; j++) {
			count += Integer.valueOf(String.valueOf(c[j]));
		}
		return count;
	}
 
	/**
	 * 递规方法 算出每个种类的对应组合
	 * 
	 * @param repeat
	 *            是否允许重复
	 * @param separator
	 *            遍历每个结果的分割符
	 */
	public void combination(StringBuffer str, ArrayList<String> list,
			int length, boolean repeat, ArrayList</string><string> addList,
			String separator) {
		if (length == 1) {
			for (int i = 0; i < list.size(); i++) {
				StringBuffer result = new StringBuffer(str);
				String tmpStr = list.get(i);
				result.append(tmpStr + separator);
				// 加入队列
				addList.add(result.toString());
			}
		}
		if (length > 1) {
			for (int i = 0; i < list.size(); i++) {
				StringBuffer temp = new StringBuffer(str);
				String tmpStr = list.get(i);
				ArrayList<String> listTmp = new ArrayList</string><string>(list);
				if (!repeat) {
					listTmp.remove(i);
				}
				combination(temp.append(tmpStr + separator), listTmp,
						length - 1, repeat, addList, separator);
			}
		}
	}
 
}
</string>