fencerepair.java

PKU中一些数据结构基本算法题的java实现

package PKU;

import java.util.*;
class ArrayListHeap{
	private ArrayList<Comparable> list = new ArrayList<Comparable>();
	boolean kind;
	public ArrayListHeap(boolean kind){
		this.kind = kind;
	}
	
	public void addElement(Comparable e) {
		list.add(e);
		if(size()>1){
			heapifyAdd();
		}
		
	}

	public Comparable findMinOrMax() {
		return list.get(0);
	}

	public boolean isEmpty() {
		return list.isEmpty();
	}

	public Comparable removeMinOrMax() {
		if(isEmpty()) return null;
		Comparable result = list.get(0);
		if(size()>1)
			heapifyRemove();
		else list.clear();
		return result;
	}
    private void heapifyRemove(){
    	list.set(0, list.remove(size()-1));
    	int parent = 0;
    	int child = 2*parent + 1;
    	while(child <= size()-1){
    		if(!(child==size()-1) && getCondition(list.get(child),list.get(child+1))){
    			child++;
    		}
    		if(!getCondition(list.get(child),list.get(parent))){
    			Comparable temp = list.get(parent);
				list.set(parent, list.get(child));
				list.set(child, temp);
				parent = child;
				child = 2*parent + 1;
    		}
    		else break;
    	}
    }
	public int size() {
		return list.size();
	}
	private boolean getCondition(Comparable a, Comparable b){
		if(kind==true){
			return a.compareTo(b)<0;
		}
		else return a.compareTo(b)>0;
	}
	private void heapifyAdd(){
		Comparable temp;
		int child = size()-1;
		int parent = (child-1) / 2;
		while(parent>=0){
			if(getCondition(list.get(parent),list.get(child))){
				temp = list.get(parent);
				list.set(parent, list.get(child));
				list.set(child, temp);
				child = parent;
				parent = (child-1) / 2;
			}
			else break;
		}
	}


	
}

/**
 * ID:3253
 * 霍夫曼树
 * @author yhm
 *
 */
public class FenceRepair {

	/**
	 * @param args
	 */
	public static void main(String[] args) {		
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()){
			long size = cin.nextLong();
			ArrayListHeap heap = new ArrayListHeap(false);
			for(int i=0;i<size;i++){
				heap.addElement(cin.nextLong());
			}
			long r = solve(heap);
			System.out.println(r);
		}
	}
	
	static long solve(ArrayListHeap heap){
		long result=0;
		while(heap.size()>1){
			long min1 = (Long)heap.removeMinOrMax();
			long min2 = (Long)heap.removeMinOrMax();
			long temp = min1+min2;
			result+=temp;
			heap.addElement(temp);
		}
		return result;
	}

}