Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-09-05

TallPeople

| 10:33

問題文, SRM 208

How To Dissect a TopCoder Problem Statement -- Algorithm Tutorialsから。

一番小さい人の中から一番大きい人を選び、一番大きい人の中から一番小さい人を選ぶ。

210.68/250

class TallPeople {
public:
    vector <int> getPeople(vector <string> people) {
        R = people.size();
        ppl = vector<vector<int> >(R);
        for (int i = 0; i < R; i++) {
            istringstream iss(people[i]);
            int t;
            while (iss >> t) ppl[i].push_back(t);
        }
        C = ppl[0].size();

        vector <int> result(2);
        result[0] = tallestOfShortest();
        result[1] = shortestOfTallest();
        return result;
    }
private:
    int R, C;
    vector<vector<int> > ppl;
    int tallestOfShortest() {
        int tallest = INT_MIN;
        for (int i = 0; i < R; i++)
            tallest = max(tallest, 
                    *min_element(ppl[i].begin(),ppl[i].end()));
        return tallest;
    }
    int shortestOfTallest() {
        int shortest = INT_MAX;
        for (int i = 0; i < C; i++) {
            int tallest = INT_MIN;
            for (int j = 0; j < R; j++)
                tallest = max(tallest, ppl[j][i]);
            shortest = min(shortest, tallest);
        }
        return shortest;
    }
};