题目链接

K Best POJ - 3111

思路

$$ 01分数规划，输出最优解，这题时间卡的好紧 $$

时间复杂度

$$ O(Nlog(N)log(max(a_i))) $$

代码

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <functional>

using namespace std;


const int N = 1e5 + 10;
const double eps = 1e-6;
class zero_one_plan {
public:
    double f[N];
    // 1 base
    double solve(int *_a, int *_b, int n, int k) {
        double l = 0, r = *max_element(_a + 1, _a + 1 + n);
        while (fabs(r - l) > eps) {
            double mid = (l + r) / 2;
            for (int i = 1; i <= n; i++) {
                f[i] = 1.0 * _a[i] - mid * _b[i];
            }
            nth_element(f + 1, f + 1 + k, f + 1 + n, greater<double>());
            double sum = 0;
            for (int i = 1; i <= k; i++) {
                sum += f[i];
            }
            if (sum > -eps) {
                l = mid;
            } else {
                r = mid;
            }
        }
        return l;
    }

    vector<int> res(int *_a, int *_b, int n, int k, double mid) {
        vector<pair<double, int> > ff(n + 1);
        for (int i = 1; i <= n; i++) {
            ff[i].first = 1.0 * _a[i] - mid * _b[i];
            ff[i].second = i;
        }
        nth_element(ff.begin() + 1, ff.begin() + 1 + k, ff.end(), greater<pair<double, int> >());
        vector<int> ans(k);
        for (int i = 1; i <= k; i++) {
            ans[i - 1] = ff[i].second;
        }
        return ans;
    }

} zo;

const int MAXN = 1e5 + 10;
int a[MAXN], b[MAXN];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);// don't forget &

    for (int i = 1; i <= n; i++) {
        scanf("%d %d", &a[i], &b[i]);// don't forget &
    }
    double ans = zo.solve(a, b, n, k);
    vector<int> w = zo.res(a, b, n, k, ans);
    for (int i = 0; i < (int)w.size(); i++) {
        printf("%d%c", w[i], " \n"[i == (int)w.size() - 1]);
    }
    return 0;
}