POJ 1011 Sticks

Description

Input

Output

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

/*
* java实现
*/

import java.util.LinkedList;
import java.util.Scanner;

public class Main {

　　private final byte N;
　　private byte[] segments;
　　private boolean[] marked;
　　private int originShortestLength;
　　private int sumLength;

　　Main(byte n, byte[] segements) {
　　　　this.N = n;
　　　　this.segments = sort(segements);
　　　　originShortestLength = 0;
　　　　for(int i = 0; i < N; i++)
　　　　　　sumLength += this.segments[i];
}

　　public byte[] sort(byte[] array) {
　　　　for(int i = 1; i < array.length; i++) {
　　　　　　for(int j = i; j > 0 && array[j] > array[j-1]; j--) {
　　　　　　　　byte temp = array[j];
　　　　　　　　array[j] = array[j-1];
　　　　　　　　array[j-1] = temp;
　　　　　　}
　　　　}
　　　　return array;
　　}

　　public int originShortestLength() {
　　　　return originShortestLength;
　　}

　　@SuppressWarnings("unused")
　　public boolean hasOriginShortestLength() {
　　　　byte n = (byte) (N - 1);
　　　　//boolean find = true;
　　　　for(; n > 0; n--) {
　　　　　　if(sumLength%n == 0) {
　　　　　　　　int average = sumLength/n;
　　　　　　　　//byte base = (byte) ((byte) + (byte)segments[N-1]);
　　　　　　　　if(segments[0] > average)
　　　　　　　　continue;
　　　　　　　　marked = new boolean[N];
　　　　　　　　byte start;
　　　　　　　　for(int i = 0; i < n; i++) {
　　　　　　　　　　int sum = 0;
　　　　　　　　　　for(start = 0; start < N; start++)
　　　　　　　　　　　　if(!marked[start]) {
　　　　　　　　　　　　　　marked[start] = true;
　　　　　　　　　　　　　　sum = segments[start];
　　　　　　　　　　　　　　break;
　　　　　　　　　　　　}
　　　　　　　　　　　　if(!dfs(average, sum, start, (byte)(N-1)))
　　　　　　　　　　　　return false;
　　　　　　　　}
　　　　　　originShortestLength = average;
　　　　　　return true;
　　　　　　}
　　　　}
　　return false;
　　}

　　public boolean dfs(int average, int sum, byte low, byte high) {
　　　　if(low >= high)
　　　　　　return false;
　　　　if(marked[high]){
　　　　　　if(dfs(average, sum, low, (byte) (high-1)))
　　　　　　return true;
　　　　}
　　　　else if(sum + segments[high] > average)
　　　　　　return false;
　　　　else if(sum + segments[high] < average) {
　　　　　　marked[high] = true;
　　　　　　if(!dfs(average, sum + segments[high], low, (byte) (high-1))) {
　　　　　　　　marked[high] = false;
　　　　　　　　if(dfs(average, sum, low, (byte) (high-1)))
　　　　　　　　return true;
　　　　　　}
　　　　　　else
　　　　　　return true;
　　　　}
　　　　else {
　　　　　　marked[high] = true;
　　　　　　return true;
　　　　}
　　　　return false;
　　}

　　public static void main(String[] args) {
　　　　Scanner in = new Scanner(System.in);
　　　　LinkedList<Integer> results = new LinkedList<Integer>();
　　　　while(in.hasNext()) {
　　　　　　byte n = in.nextByte();
　　　　　　if(n == 0)
　　　　　　　　break;
　　　　　　byte[] segements = new byte[n];
　　　　　　for(int i = 0; i < n; i++) {
　　　　　　　　segements[i] = in.nextByte();
　　　　　　}
　　　　　　Main m = new Main(n, segements);
　　　　　　if(m.hasOriginShortestLength())
　　　　　　　　results.add(m.originShortestLength());
　　　　　　else
　　　　　　　　System.out.println("no answer");
　　　　　　}
　　　　　　for(int b : results)
　　　　　　　　System.out.println(b);
　　　　　}

　　　}

POJ 1011 Sticks,布布扣,bubuko.com

POJ 1011 Sticks

原文：http://www.cnblogs.com/boole/p/3593435.html