網頁

2013年8月16日 星期五

c010. What is the Median?、UVA 10107 (insert sort)

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std ;

int main(){
    vector<int>  numbers ;
    int num, i=0 ;
    while(cin >> num){
        if(numbers.size() <= 0){
            numbers.push_back(num) ;
            cout << num << endl ;
            continue ;
        }
        vector<int>::iterator it = numbers.begin() ;
        if(num <= numbers.front())
            numbers.insert(it,num) ;
        else if(num >= numbers.back())
            it=numbers.end(), numbers.insert(it,num) ;
        else{
            for(it=numbers.begin() ; it<numbers.end()-1 ; it++){
                if(*(it+1)>num && *it<num || *it == num){
                    numbers.insert(it+1,num) ;
                    break ;
                }
            }
        }
        /*
        for(it=numbers.begin() ; it<numbers.end() ; it++){
            cout << *it << " ";
        }
        cout << endl ;
        */
        if(numbers.size()%2){
            cout << numbers[(numbers.size()-1)/2] << endl ;
        }
        else{
            cout << (numbers[(numbers.size()-1)/2]+numbers[numbers.size()/2])/2 << endl ;
        }
    }
    return 0 ;
}

沒有留言:

張貼留言