SRM 535 div1 med: FoxAndBusiness

問題

TopCoder Statistics - Problem Statement

解法

とりあえずいろいろ書いてみましょう。

0, 1, ..., K-1 の社員を選択するとします。この時, ability の和を A とすると, 各社員は等しい時間働くので, 各社員のはたらく時間は totalWork / A です。で, 各社員 i は, 全体の仕事の内 ai/A だけの仕事をこなすので, 給料は pi * (ai / A) * totalWork だけ払います。結局, 合計コストは
totalWork * sum((3600 + pi*ai)/A) となります。totalWork は固定なので, これは sum((3600 + pi*ai)/A) の最小化問題になります。これはよくある「(目標値) = x として x について二分探索する」というテクが使えますね。

sum((3600 + pi*ai)/A) <= x という条件は, sum(3600 + pi*ai) <= x*sum(ai) i.e. sum((x-pi)*ai) >= 3600*K と同値です。これを満たすかで x の二分探索をしましょう。

bool check(double x, const int K, const vector<int>& a, const vector<int>& p) {
    int N = a.size();
    vector<double> v(N);
    for (int i = 0; i < N; i++) v[i] = (x-p[i])*a[i];
    sort(v.rbegin(), v.rend());
    double sum = 0;
    for (int i = 0; i < K; i++) sum += v[i];
    return sum >= 3600*K;
}

class FoxAndBusiness {
public:
    double minimumCost(int K, int totalWork, vector <int> a, vector <int> p) {
        double low = 0, high = 1e9;
        for (int i = 0; i < 100; i++) {
            const double med = (low+high)/2;
            if (check(med, K, a, p)) high = med;
            else low = med;
        }
        return totalWork * high;
    }
};