SRM 483 div1 hard: Sheep

問題

TopCoder Statistics - Problem Statement

解法

「こんなの二分探索するだけでしょｗｗｗｗ」って感じですが, それだけだと落ちます。単調性を持たないからです。

ただ, ある数 C が最小の答えであるとすると, C+maxw でも羊を運ぶことが出来ます(maxw は羊の最大質量)。よって, 二分探索でとりあえず C の上界を見つけたら, C-2000 から順に答えを探していけば良いです。

bool ok(int x, const vector<int>& sheep, int maxRuns) {
    int cnt = 0;
    map<int, int> mp;
    for (int el : sheep) mp[el]++;
    int rest = x;
    while (cnt < maxRuns) {
        if (mp.empty()) return true;
        auto it = mp.lower_bound(rest);
        if (it == mp.end()) it--;
        if (it != mp.begin() && (it->first) > rest) {
            it--;
        }
        if (it == mp.begin() && rest < (it->first)) {
            rest = x;
            cnt++;
            continue;
        }
        it->second -= 1;
        rest -= it->first;
        if (it->second == 0) mp.erase(it);
    }
    return false;
}

class Sheep {
public:
    int minCapacity(int numSheep, int maxRuns, vector <string> part1, vector <string> part2, vector <string> part3, vector <string> part4) {
        vector<int> sheep(numSheep);
        {
            string s;
            for (string t : part1) s += t;
            for (string t : part2) s += t;
            for (string t : part3) s += t;
            for (string t : part4) s += t;
            stringstream ss(s);
            for (int i = 0; i < numSheep; i++) ss >> sheep[i];
        }
        int low = 0, high = 2000*2000;
        while (high-low > 1) {
            int med = (high+low)/2;
            if (ok(med, sheep, maxRuns)) high = med;
            else low = med;
        }
        int ans = max(0, high-2000);
        while (1) {
            if (ok(ans, sheep, maxRuns)) return ans;
            ans++;
        }
    }
};