Guest User

Untitled

a guest
Dec 13th, 2017
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.39 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <stdio.h>
  5.  
  6. using namespace std;
  7.  
  8. vector<unsigned int> a;
  9. vector<unsigned int> b;
  10. double last_success_x;
  11. vector<pair<double, unsigned int> > rest;
  12.  
  13. double diff;
  14.  
  15. bool sortinrev(const pair<double, unsigned int> &a, const pair<double, unsigned int> &b)
  16. {
  17. return (a.first > b.first);
  18. }
  19.  
  20. bool iteration(unsigned int n, unsigned int k, double x)
  21. {
  22. unsigned int i;
  23.  
  24. for (i = 0; i < n; ++i)
  25. {
  26. rest[i] = make_pair(a[i] - b[i] * x, i);
  27. }
  28.  
  29. sort(rest.begin(), rest.end(), sortinrev);
  30.  
  31. double sum = 0.;
  32. for (i = 0; i < k; ++i)
  33. {
  34. sum += rest[i].first;
  35. }
  36.  
  37. return sum >= 0;
  38. }
  39.  
  40. void solve(unsigned int n, unsigned int k, double r_lim)
  41. {
  42. double left = last_success_x = 0.;
  43. double right = r_lim;
  44. double x = (left + right) / 2;
  45.  
  46. unsigned int i;
  47.  
  48. rest = vector<pair<double, unsigned int> >(n);
  49.  
  50. while (right - left >= diff)
  51. {
  52. // cout << "right = " << right << " left = " << left << endl;
  53. if (iteration(n, k, x))
  54. {
  55. left = last_success_x = x;
  56. }
  57. else
  58. {
  59. right = x;
  60. }
  61.  
  62. x = (left + right) / 2;
  63. }
  64.  
  65. // cout << "last_success_x = " << last_success_x << endl;
  66. iteration(n, k, last_success_x);
  67.  
  68. for (i = 0; i < k; ++i)
  69. {
  70. printf("%d ", rest[i].second + 1);
  71. //cout << rest[i].second + 1 << " ";
  72. }
  73.  
  74. printf("\n");
  75. // cout << endl;
  76. }
  77.  
  78. int main()
  79. {
  80. unsigned int requests_num;
  81. unsigned int n, k;
  82. unsigned int i, j;
  83. unsigned int temp;
  84. double max_a, min_b, max_b;
  85.  
  86. scanf("%u", &requests_num);
  87.  
  88. for (i = 0; i < requests_num; ++i)
  89. {
  90. scanf("%u %u", &n, &k);
  91. max_a = 0;
  92. min_b = 1000001;
  93. max_b = 0;
  94.  
  95. a = vector<unsigned int>(n);
  96. b = vector<unsigned int>(n);
  97.  
  98. for (j = 0; j < n; ++j)
  99. {
  100. scanf("%u", &temp);
  101. max_a = temp > max_a ? temp : max_a;
  102. a[j] = temp;
  103. }
  104. for (j = 0; j < n; ++j)
  105. {
  106. scanf("%u", &temp);
  107. max_b = temp > max_b ? temp : max_b;
  108. min_b = temp < min_b ? temp : min_b;
  109. b[j] = temp;
  110. }
  111.  
  112. // cout << "max_a = " << max_a << endl;
  113.  
  114. diff = 2. / UINT32_MAX;
  115. //cout << max_a << " " << min_b << " " << max_b << endl;
  116. solve(n, k, max_a / min_b);
  117. }
  118.  
  119. return 0;
  120. }
Add Comment
Please, Sign In to add comment