Emiliatan

最大化平均值

Feb 21st, 2019
180
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.81 KB | None | 0 0
  1. #include <cstdio>
  2. #include <algorithm>
  3. using namespace std;
  4.  
  5. const int MAXN = 1001, INF = 1000;
  6.  
  7. int n, k;
  8. int w[MAXN], v[MAXN];
  9.  
  10. double tmp[MAXN];
  11.  
  12. bool isGood(double x)
  13. {
  14.     double sum = 0;
  15.     for(int i = 0; i < n; i++)
  16.         tmp[i] = v[i] - w[i] * x;
  17.  
  18.     sort(tmp, tmp + n, greater<double>());
  19.  
  20.     for(int i = 0; i < k; i++)
  21.         sum += tmp[i];
  22.  
  23.     return (sum >= 0);
  24. }
  25.  
  26. double getResult()
  27. {
  28.     double L = 0, R = INF, mid;
  29.     for(int i = 0; i < 50; i++)
  30.         if(isGood(mid = (L + R) / 2)) L = mid;
  31.         else R = mid;
  32.     return L;
  33. }
  34. int main()
  35. {
  36.     scanf("%d %d", &n, &k);
  37.  
  38.     for(int i = 0; i < n; i++)
  39.         scanf("%d %d", &w[i], &v[i]);
  40.  
  41.     printf("%.2f\n",getResult());
  42.  
  43.     return 0;
  44. }
Add Comment
Please, Sign In to add comment