最大化平均值

　　題目大意：給定你n個分數，從中找出k個數，使∑a/∑b的最大值

　　這一題同樣的也可以用二分法來做（用DP會超時，可見二分法是多么的實用呵！），大體上是這樣子：假設最大的平均值是w，那么題目就是問存不存在∑a/b>=w,我們把這條式子變形

　　　　　　∑a-w∑b>=0

?　 那么這一題就變成了尋找k個最大的a-w*b，使∑a-w∑b>=0成立

　　

1 #include <iostream> 2 #include <algorithm> 3 #include <functional> 4 5 using namespace std; 6 7 static double mid, y[1001]; 8 struct _set 9 { 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/b>=w移項 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

總結

以上是生活随笔為你收集整理的Divide and conquer:Dropping tests(POJ 2976)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。