SHARE
TWEET

Untitled

a guest Sep 18th, 2019 93 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
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top