题解 | #小咪买东西#
小咪买东西
https://ac.nowcoder.com/acm/problem/14662
可以采用二分总价值的方式，已知总价值为x了，那么需要对分数进行价值和/花费和>=0进行变形得：总（价值-x*花费）>=0.势必要贪心的选取价值-x*花费最大的前k个东西。那么就可以得到是否满足。之后二分就行。
值得注意的是本题的答案是在实数范围内的。所以采用足够的循环来界定要二分多少次，一防止出现死循环的现象。
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int n, k;
const int maxn = 1e4+10;
int a[maxn][2];
bool yanz(double x) {
double b[maxn];
ll ans = 0;
for (int i=0;i<n;i++) {
b[i] = a[i][1]-x*a[i][0];
}
sort(b, b+n, greater());
for (int i=0;i<k;i++) {
ans += b[i];
}
return ans>=0;
}
int main() {
int T;
cin>>T;
while (T--) {
cin>>n>>k;
for (int i=0;i<n;i++) {
cin>>a[i][0]>>a[i][1];
}
double l=0, r = 1e8;
for (int i=0;i<100;i++) {
// cout<<l<<" "<<r<<endl;
double mid = (l+r)/2;
if (yanz(mid)) {
l = mid;
}else {
r = mid;
}
}
printf("%.0lf\n", floor(l));
}
return 0;
}
