Divide and conquer:K Best(POJ 3111)

 1 #include <iostream>
 2 #include <functional>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 struct _set
 7 {
 8     int v, w, num;
 9 }jewels[100001];
10 struct _out_set
11 {
12     double price;
13     int num;
14     bool operator<(const _out_set &x)const
15     {
16         return price < x.price;
17     }
18 }y[100001];
19 static int s2[100001];
20 
21 bool judge(double, const int, const int);
22 
23 int main(void)//最大化平均值标准题型，要求输出组合
24 {
25     int n, k;
26     double lb, rb, mid; 
27 
28     while (~scanf("%d%d", &n, &k))
29     {
30         for (int i = 0; i < n; i++)
31         {
32             scanf("%d%d", &jewels[i].v, &jewels[i].w);
33             jewels[i].num = i + 1;
34         }
35         lb = 0; rb = 10e+7+1; 
36 
37         for (; rb - lb > 10e-7;)//精度起码10e-7以上，不能10e-8,不然tle
38         {
39             mid = (lb + rb) / 2;
40             if (judge(mid, n, k))lb = mid;
41             else rb = mid;
42         }
43         for (int i = 0; i < k; i++)
44             printf("%d ", s2[i]);
45         printf("\n");
46     }
47     return 0;
48 }
49 
50 bool judge(double mid, const int n, const int k)
51 {
52     double sum = 0;
53     for (int i = 0; i < n; i++)
54     {
55         y[i].price = jewels[i].v - mid*jewels[i].w;
56         y[i].num = jewels[i].num;
57     }
58     sort(y, y + n);//内建排序一定要对，不然又要出错了T T
59 
60     for (int i = 0; i < k; i++)
61     {
62         sum += y[n - i - 1].price;
63         s2[i] = y[n - i - 1].num;
64     }
65     return sum >= 0;
66 }