2018年东北农业大学春季校赛 I-wyh的物品(二分查找)-白红宇

2018年东北农业大学春季校赛 I-wyh的物品(二分查找)

阅读量：5072 次

发布时间：2019-06-12

本文共 1446 字，大约阅读时间需要 4 分钟。

链接：

来源：牛客网

题目描述

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[i]/w[i]<=x -> ∑v[i]<=x*∑w[i] -> ∑(v[i]-x*w[i])<=0

#include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #include
                      
                       #include
                       #define lson l, m, rt<<1#define rson m+1, r, rt<<1|1#define IO ios::sync_with_stdio(false);cin.tie(0);#define INF 0x3f3f3f3f#define MAXN 100010const int MOD=1e9;typedef long long ll;using namespace std;int n, t, k, w[100010], v[100010];double y[100010];int C(double x){ for(int i = 0; i < n; i++){ y[i] = v[i]-x*w[i]; } sort(y, y+n); double sum = 0; for(int i = 0; i < k; i++){ sum += y[n-i-1]; } return sum >= 0;//转成与0比较}int main(){ cin >> t; while(t--){ cin >> n >> k; for(int i = 0; i < n; i++){ cin >> w[i] >> v[i]; } double lb = 0, ub = INF; for(int i = 0; i < 100; i++){ double mid = (lb+ub)/2; if(C(mid)){ lb = mid; } else{ ub = mid; } //cout << mid << endl; } printf("%.2lf\n", lb); } return 0;}

转载于:https://www.cnblogs.com/Surprisezang/p/8722476.html

你可能感兴趣的文章