题目描述 

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

说明

对于样例来说，我们选择第一个物品和第三个物品，达到最优目的

思路

前提我们要知道的一个公式：

物品价值(v) = 单位价值*物品重量(w)

• 1
• 2

对于任意的单位价值m，我们都可以发现： 

1、对于任意的一个物品，物品实际价值与对于任意单位价值的关系只有三种情况：

1、x = 物品实际价值（v） -  (任意单位价值(mid)*物品重量(w)) == 0;这说明：任意单位价值(mid)==实际单位价值。2、x = 物品实际价值（v） -  (任意单位价值(mid)*物品重量(w)) > 0;这说明：任意单位价值(mid)
    <实际单位价值。3、x = 物品实际价值（v） - (任意单位价值(mid)*物品重量(w)) < 0;这说明：任意单位价值(mid)>
     实际单位价值。
    

• 1
• 2
• 3
• 4
• 5
• 6
• 7

这里对应着核心代码：s[i] = v[i] - mid*w[i];

 2、我们将所有这些实际价值与单位价值之差分别存储到一个数组当中，为了保证任意单位价值最大，我们取前k大的差值(x)。 

这里不太好想，我们换一个思路去思考，x值越大，就说明mid值越小，就说明还有比mid更大实际单位价值的值需要我们去找，我们的目的就是要找到更大的mid值呀。 

这里对应着核心代码：sort(s,s+n,cmp);

3、我们把选择出的前k个差值相加，得到前k个差值最大的物品实际价值与物品对于任意单位价值（n）所求得的物品相对价值之差的之和（ss）。 

这个值有两种情况

ss>=0 //任意的单位价值n取小了，导致实际价值还有剩余，还有更大的n。ss<0  //任意的单位价值n取大了，导致实际价值都不可能满足由这个单位价值算出来的总价值。

AC：代码

#include
    
     #include
     
      #include
      
       #include
       
        const int maxn = (int)1e5+5; int w[maxn],v[maxn];double s[maxn]; int n,k;using namespace std;int cmp(double x,double y){	return x>y;}int slove(double mid){	double ss = 0;	for(int i = 0;i
        
         =0) return 1;	else return 0;}int main(){	int t;	cin>>t;	while(t--)	{		scanf("%d %d",&n,&k);		double low = 0,high = 100000,mid;		for(int i = 0;i
         
          0.00001) { mid = (low + high)/2.0; if(slove(mid)) low = mid; else high = mid; } printf("%.2lf\n",low); } return 0;}