Tuesday 8 May 2012

UVa 10107 What is the Median? Solution

#include<iostream>
#include<algorithm>

using namespace std;
int main()
{
    long long a[100000],n,i=0,l;
    while(cin>>n)
    {
        a[i]=n;

            sort(a,a+i+1);
        if(i%2==0)
            cout<<a[i/2]<<endl;
        else
        {
            l=a[i/2]+a[i/2+1];
            cout<<l/2<<endl;
        }

        i++;
    }
return 0;
}

2 comments:

  1. I thought this problem is harder than it looks like so I code O(nlogn) solution instead of O(n^2logn) ... http://ideone.com/yky4tf

    ReplyDelete
  2. Inefficient solution. Complexity of the solution is bad.

    ReplyDelete