小咪买东西（最大化平均值）

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 131072K，其他语言262144K

64bit IO Format: %lld

题目描述

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

输入描述:

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

输出描述:

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

示例1

输入

1
5 1
1 2
2 3
3 4
4 5
5 6

输出

2

备注:

1≤T≤101≤n≤10⁴1≤k≤n白书144页最大化平均值原题附ac代码：

1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <string>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 1e4+10;
 8 typedef long long ll;
 9 int t;
10 int n,k;
11 struct nod
12 {
13     int c;
14     int v;
15 }nu[maxn];
16 double y[maxn];
17 double judg(int x)
18 {
19     for(int i=0;i<n;++i)
20     y[i]=nu[i].v-nu[i].c*x;
21     sort(y,y+n);
22     double sum=0;
23     for(int i=0;i<k;++i)
24     sum+=y[n-i-1];
25     return sum;
26 }
27 int main()
28 {
29 
30     scanf("%d",&t);
31     while(t--)
32     {
33         scanf("%d%d",&n,&k);
34         for(int i=0;i<n;++i)
35         {
36             scanf("%d%d",&nu[i].c,&nu[i].v);
37         }
38         int mid;
39         int l=0,r=maxn;
40         while(l<=r)
41         {
42             mid=l+(r-l)/2;
43             if(judg(mid)<0) r=mid-1;
44             else l=mid+1;
45         }
46         printf("%dn",r);
47     }
48 
49     return 0;
50 }

View Code

原文链接: https://www.cnblogs.com/zmin/p/8060278.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍