01分数规划

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

小咪是一个土豪手办狂魔，这次他去了一家店，发现了好多好多（n个）手办，但他是一个很怪的人，每次只想买k个手办，而且他要让他花的每一分钱都物超所值，即：买下来的东西的总价值/总花费=max。请你来看看，他会买哪些东西吧。

输入描述:

多组数据。
第一行一个整数T，为数据组数。
接下来有T组数据。
对于每组数据，第一行两个正整数n，k，如题。
接下来n行，每行有两个正整数ci，vi。分别为手办的花费和它对于小咪的价值。

输出描述:

对于每组数据，输出一个数，即能得到的总价值/总花费的最大值。精确至整数。
示例1

输入

复制 
1
5 1
1 2
2 3
3 4
4 5
5 6

输出

复制 
2

备注:

1≤T≤10
1≤n≤104
1≤k≤n
1≤ci,vi≤104

01分数规划的模板题，找到选定答案中最大的k个康康是不是正数即可。二分答案。最后输出给精度卡了一下，我加了个eps保证样例正确，虽然不加也A了。

时间复杂度

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include <bits/stdc++.h>
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1e9 + 7;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar())    s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void write(ll x) { if (!x) { putchar('0'); return; } char F[40]; ll tmp = x > 0 ? x : -x; if (x < 0)putchar('-');  int cnt = 0;    while (tmp > 0) { F[cnt++] = tmp % 10 + '0';     tmp /= 10; }    while (cnt > 0)putchar(F[--cnt]); }
inline ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll qpow(ll a, ll b) { ll ans = 1;   while (b) { if (b & 1)  ans *= a;       b >>= 1;      a *= a; }   return ans; }   ll qpow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1)(ans *= a) %= mod; b >>= 1; (a *= a) %= mod; }return ans % mod; }
inline int lowbit(int x) { return x & (-x); }

const int N = 1e4 + 7;
const double eps = 1e-7;
struct Node {
    double c, v, d;
    bool operator < (const Node& b) const {
        return d > b.d;
    }
}a[N];
int n, m;

bool check(double x) {
    for (int i = 1; i <= n; ++i) a[i].d = a[i].v - a[i].c * x;
    sort(a + 1, a + 1 + n);
    double ans = 0.0;
    for (int i = 1; i <= m; ++i) ans += a[i].d;
    return ans > eps;
}

int main() {
    js;
    int T; cin >> T;
    while (T--) {
        cin >> n >> m;
        for (int i = 1; i <= n; ++i) cin >> a[i].c >> a[i].v;
        double l = eps, r = 1e9, mid;
        for (int i = 0; i < 100; ++i) { // 防止精度卡死，mid不动的情况TLE
            mid = (l + r) / 2.0;
            if (check(mid)) l = mid;
            else r = mid;
        }
        printf("%d\n", (int)(mid + eps));
    }
    return 0;
}