Guest User

Untitled

a guest
Sep 18th, 2019
98
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  5. int const maxn = 1e5;
  6. long long const mod = 1000000007;
  7. int n, k;
  8. double ttt = 0.0;
  9. vector<double> a, b;
  10. vector<int> current, order;
  11.  
  12. void input() {
  13. cin >> n >> k;
  14. double temp;
  15. for (int i = 0; i < n; i++) {
  16. cin >> temp;
  17. a.push_back(temp);
  18. cin >> temp;
  19. b.push_back(temp);
  20. current.push_back(i);
  21. }
  22. for (int i = 0; i < k; i++) {
  23. order.push_back(0);
  24. }
  25. }
  26.  
  27. inline bool cmp(const int &f1, const int &f2) {
  28. return ((ttt * b[f1] + a[f1]) / (b[f1]) > (ttt * b[f2] + a[f2]) / (b[f2]));
  29. }
  30.  
  31. inline bool possible() {
  32. sort(current.begin(), current.end(), cmp);
  33. double up = 0.0, down = 0.0;
  34. for (int i = 0; i < k; i++) {
  35. up += a[current[i]];
  36. down += b[current[i]];
  37. }
  38. if (ttt <= up / down) {
  39. for (int i = 0; i < k; i++) {
  40. order[i] = current[i] + 1;
  41. }
  42. return true;
  43. } else {
  44. return false;
  45. }
  46. }
  47.  
  48.  
  49. void solve() {
  50. double l = 0.0, r = 10000000.0;
  51. while (r - l > 0.000001) {
  52. ttt = (l + r) / 2.0;
  53. if (possible()) {
  54. l = ttt;
  55. } else {
  56. r = ttt;
  57. }
  58. }
  59. for (int i = 0; i < k; i++) {
  60. cout << order[i] << " ";
  61. }
  62.  
  63. }
  64.  
  65. int32_t main() {
  66. freopen("kbest.in", "r", stdin);
  67. freopen("kbest.out", "w", stdout);
  68. IOS
  69. input();
  70. solve();
  71. return 0;
  72.  
  73. }
RAW Paste Data