01204212/icecream

This is part of 01204212

Tasks: icecream shop 3, icecream shop 4

Test data: icecream3, icecream4

Links

• Java priority queue class
• An example on how to add custom objects to the priority queue: stackoverflow

Codes

Customer class (for icecream3)

public class Customer implements Comparable<Customer> {
	public int age;
	public int id;
		
	public Customer(int i, int a) {
		id = i; age = a;
	}

	@Override
	public int compareTo(Customer a) {
		if(age < a.age) {
			return -1;
		} else if(age > a.age) {
			return 1;
		} else {
			return 0;
		}
	}	
}

Main class (for icecream3)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;

public class Main {
	void process() throws NumberFormatException, IOException {
	    BufferedReader reader = new BufferedReader(
	               new InputStreamReader(System.in) );

	    int m = Integer.parseInt(reader.readLine()); 
	    for(int i=0; i<m; i++) {
	    	String items[] = reader.readLine().split(" ");
	    	if((items.length == 1) && (items[0].equals("2"))) {
	    		// get the first customer out
	    	} else {
	    		int numNewCustomer = Integer.parseInt(items[1]);
	    		for(int j=0; j<numNewCustomer; j++) {
	    			int id = Integer.parseInt(items[2 + j * 2]);
	    			int age = Integer.parseInt(items[2 + j * 2 + 1]);
	    			// add this customer to the queue
	    		}
	    	}
	    }
	}
	
	public static void main(String[] args) throws IOException  {
		Main m = new Main();
		
		m.process();
	}
}

Partial implementation of Min Heap

public class PQ<T extends Comparable<T>> {
	static final int MAX_ELEMENTS = 2000000;
	private T [] items;
	private int n;

	PQ() {
		items = (T[]) new Comparable[MAX_ELEMENTS];
		n = 0;
	}

	int parent(int i) {
		return (i-1)/2;
	}
	
	int leftChild(int i) {
		return i*2 + 1;
	}
	
	int rightChild(int i) {
		return i*2 + 2;
	}
	
	public void add(T elt) {
		items[n] = elt;
		n++;
		
		percolateUp(n-1);
	}

	private void swap(int a, int b) {
		T temp = items[a];
		items[a] = items[b];
		items[b] = temp;
	}

	public T poll() {
		T m = items[0];
		
		items[0] = items[n-1];
		items[n-1] = null;
		n--;
		
		percolateDown(0);
		return m;
	}

	private void percolateUp(int i) {
		while(i != 0) {
			int p = parent(i);
			if(items[i].compareTo(items[p]) < 0) {
				swap(i,p);
				i = p;
			} else {
				break;
			}
		}
	}
	
	private void percolateDown(int i) {
		// your job here...
		
	}
}

Sample outputs

icecream3

Answer for n1000a.in (first 15 lines):

941855
652484
873447
822903
892748
432709
379980
679815
538760
374795
921908
174871
751693
371595
14346

Answer for n100000b.in (first 15 lines):

541932
125245
165780
827150
487479
824741
913162
493532
563729
714886
315377
445543
532953
22524
168978

icecream4

Answer for n100000a.in (first 15 lines):

157726
646406
135578
877759
646159
612081
488145
982535
955624
154100
762687
520843
743231
144842
378444

Answer for n100000d.in (first 15 lines):

763548
739589
663667
64820
317254
375870
934699
743202
338115
31066
251780
274842
881545
76890
820892