Emiliatan

c904

Feb 21st, 2019
195
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. /* c904             */
  2. /* AC (0.1s, 112KB) */
  3.  
  4. #include <cstdio>
  5. #include <algorithm>
  6.  
  7. using namespace std;
  8.  
  9. const int MAXN = 1001,INF = 900;
  10. int N, M, K, w[MAXN], v[MAXN];
  11. double res[MAXN], sum;
  12.  
  13. bool cmp(const double &a, const double &b)
  14. {
  15.     return a > b;
  16. }
  17.  
  18. bool isOK(const double &x)
  19. {
  20.     for(int i = 0; i < N; i++)
  21.         res[i] = v[i] - x * w[i];
  22.     sort(res, res+N, cmp);
  23.     sum = 0;
  24.     for(int i = 0; i < K; i++)
  25.         sum += res[i];
  26.     return (sum >= 0);
  27. }
  28.  
  29. double getAns()
  30. {
  31.     double l = 0, r = INF, mid;
  32.     for(int i = 0; i < 24; i++)
  33.     {
  34.         mid = ( l + r ) / 2;
  35.         if( isOK(mid) ) l = mid;
  36.         else r = mid;
  37.     }
  38.     return l;
  39. }
  40.  
  41. int main()
  42. {
  43.     scanf("%d %d", &N, &M);
  44.     for(int i = 0; i < N && scanf("%d %d", &w[i], &v[i]); i++);
  45.     for(int i = 0; i < M && scanf("%d", &K); i++)
  46.         printf("%.2f\n", getAns());
  47.     return 0;
  48. }
Advertisement
Add Comment
Please, Sign In to add comment