POJ.3111 K Best

1.Problem
http://poj.org/problem?id=3111

2.Idea
Binary Search

3.Source

 int N, K;  
 int v[100005];  
 int w[100005];  
 pair<double, int> y[100005];  
 bool C(double x)  
 {  
      for (int i = 0; i < N; i++) {  
           y[i] = make_pair((double)v[i] - x * (double)w[i], i + 1);  
      }  
      sort(y, y + N);  
      double sum = 0.0;  
      for (int i = N - K; i < N; i++) sum += y[i].first;  
      return sum >= 0;  
 }  
 void solve()  
 {  
      double l = 0.0, r = 100000000.0;  
      for (int i = 0; i < 50; i++) {  
           double m = (l + r) * 0.5;  
           if (C(m)) {  
                l = m;  
           }  
           else {  
                r = m;  
           }  
      }  
      C(l);  
      for (int i = N - K; i < N; i++) {  
           printf("%d ", y[i].second);  
      }  
 }  
 int main()  
 {  
      scanf("%d%d", &N, &K);  
      for (int i = 0; i < N; i++) scanf("%d%d", &v[i], &w[i]);  
      solve();  
      return 0;  
 }