链接：

来源：牛客网

题目描述

wyh学长现在手里有n个物品，这n个物品的重量和价值都告诉你，然后现在让你从中选取k个，问你在所有可能选取的方案中，最大的单位价值为多少（单位价值为选取的k个物品的总价值和总重量的比值）

输入描述:

输入第一行一个整数T(1<=T<=10) 接下来有T组测试数据，对于每组测试数据，第一行输入两个数n和k(1<=k<=n<=100000) 接下来有n行，每行两个是a和b，代表这个物品的重量和价值

输出描述:

对于每组测试数据，输出对应答案，结果保留两位小数

示例1

输入

13 22 25 32 1

输出

0.75

说明

对于样例来说，我们选择第一个物品和第三个物品，达到最优目的 这一题乍看以为是一个很水的贪心，然后仔细看了题目，不简单。 我以为求出每一个物品的性价比出来就行了，然后选K个相加求平均值。 但是不符合题目，按我那个思想则是0.71.而题目的最优解为0.75. 否定了我的思想后，我就想不出思路了。 于是菜鸡只能去看题解了。  二分可以直接出答案。感觉二分还是强大啊。 二分条件需要公式推导，自己找出二分条件难啊！！！！ ∑val[i] / ∑weight[i] >= x; 转化  1.0*val[i]-weight[i]*mid; 就可以上代码了

1 #include
          
            2 using namespace std; 3  4 #define ll long long 5 #define llu unsigned long long 6 const int maxn=1e5+10; 7 int weight[maxn],val[maxn],n,k; 8 double cnt[maxn]; 9 int check(double mid)10 {11     double sum=0;12     for (int i=0 ;i
           
            =0) return 1;20     return 0;21 }22 23 int main(){24     int t;25     scanf("%d",&t);26     while(t--){27         scanf("%d%d",&n,&k);28         for (int i=0 ;i