优秀单页网站,青岛网络优化代理,网站建设南阳,西安住房建设局网站最大化平均值 题目大意#xff1a;给定你n个分数#xff0c;从中找出k个数#xff0c;使∑a/∑b的最大值 这一题同样的也可以用二分法来做#xff08;用DP会超时#xff0c;可见二分法是多么的实用呵#xff01;#xff09;#xff0c;大体上是这样子#xff1a;假设最… 最大化平均值 题目大意给定你n个分数从中找出k个数使∑a/∑b的最大值 这一题同样的也可以用二分法来做用DP会超时可见二分法是多么的实用呵大体上是这样子假设最大的平均值是w那么题目就是问存不存在∑a/bw,我们把这条式子变形 ∑a-w∑b0 那么这一题就变成了寻找k个最大的a-w*b使∑a-w∑b0成立 1 #include iostream2 #include algorithm3 #include functional4 5 using namespace std;6 7 static double mid, y[1001];8 struct _set9 {
10 int a,b;
11 }nums[1001];
12
13 bool judge(const int,const int);
14
15 int main(void)
16 {
17 int n, k, t;
18 double lb, rb;
19
20 while (~scanf(%d%d, n, k))
21 {
22 if (n 0 k 0)
23 break;
24 for (int i 0; i n; i)
25 scanf(%d, nums[i].a);
26 for (int i 0; i n; i)
27 scanf(%d, nums[i].b);
28 lb 0; rb 1.00, t 100;
29
30 while (t--)
31 {
32 mid (lb rb) / 2;
33 if (judge(k, n)) lb mid;
34 else rb mid;
35 }
36 printf(%d\n, int(100 * rb 0.5));
37 }
38
39 return 0;
40 }
41
42 bool judge(const int k,const int n)
43 {
44 double sum 0;
45
46 for (int i 0; i n; i)
47 y[i] nums[i].a - nums[i].b*mid;//把∑a/bw移项
48 sort(y, y n);
49
50 for (int i 0; i n - k; i)
51 sum y[n - i - 1];//要选择最大的k个而不是最小的k个
52 return sum 0;
53 } 转载于:https://www.cnblogs.com/Philip-Tell-Truth/p/5139400.html
