UVa 11875 – Brick Game

this solutions is O(nlog(n)), it can be solved in expected O(n) using order statistic partitioning. The best solution i know is O(n) using median of median algorithm.


#include <iostream>
#include <math.h>
#include <algorithm>

using namespace std ;

int main(){
	int tc,t=0,n,temp;
	int ages[12];

	cin>>tc;
	while(t++<tc){
		cin>>n;
		temp = 0;
		while(temp<n)
			cin>>ages[temp++];
		sort(ages,ages + n);
		cout<<"Case "<<t<<": "<<ages[n/2]<<endl;
	}
	return 0;
}

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s