题目链接：

题目大意：

卖宝救夫：Demy要卖珠宝，n件分别价值v_i 重 w_i，她希望保留k件使得

最大。

解题思路：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 using namespace std; 6 const int INF = 1e7; 7 const int maxn = 100005; 8 int n, m; 9 double w[maxn], v[maxn], y[maxn];10 bool judge(double x)11 {12     for(int i = 1; i <= n; i++)13         y[i] = v[i] - x * w[i];14     sort(y + 1, y + n + 1);15 16     double sum = 0;17     for(int i = 1, j = n; i <= m; i++, j--)18         sum += y[j];19     return sum >= 0;20 }21 struct node22 {23     double x;24     int id;25     bool operator <(const node& a)const26     {27         return x > a.x;28     }29 }ans[maxn];30 int main()31 {32     cin >> n >> m;33     for(int i = 1; i <= n; i++)34         cin >> v[i] >> w[i];35     double l = 0, r = INF;36     for(int i = 0; i < 50; i++)37     {38         double mid = (l + r) / 2;39         if(judge(mid))l = mid;40         else r = mid;41     }42     for(int i = 1; i <= n; i++)43     {44         ans[i].id = i;45         ans[i].x = v[i] - l * w[i];46     }47     sort(ans + 1, ans + n + 1);48     printf("%d", ans[1].id);49     for(int i = 2; i <= m; i++)50     {51         printf(" %d", ans[i].id);52     }53     puts("");54     return 0;55 }