Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-04

SMBus

| 12:55

問題文

バスの調停のシミュレーション。

class SMBus {
    public:
        int transmitTime(vector <string> messages, vector <int> times) {
            const int size = messages.size();
            vector<bool> transmitted(size, false);
            int totalTime = 0;
            for (int i = 0; i < size; i++) {
                list<int> candidates;
                for (int j = 0; j < size; j++) {
                    if (!transmitted[j]) candidates.push_back(j);
                }
                int idx = 0;
                while (candidates.size() > 1) {
                    int slowest = INT_MIN;
                    char smallest = '9'+1;
                    for (list<int>::const_iterator itr = candidates.begin(); 
                            itr != candidates.end(); itr++) {
                        if (messages[*itr].length() > idx) {
                            slowest = max(slowest, times[*itr]);
                            smallest = min(smallest, messages[*itr][idx]);
                        }
                    }
                    for (list<int>::iterator itr = candidates.begin();
                            itr != candidates.end(); ) {
                        if (messages[*itr][idx] > smallest) {
                            itr = candidates.erase(itr);
                        } else {
                            itr++;
                        }
                    }
                    totalTime += slowest;
                    idx++;
                }
                const int winner = *candidates.begin();
                totalTime += (messages[winner].length()-idx) * times[winner];
                transmitted[winner] = true;
            }

            return totalTime;
        }
};