【最大化平均值】POJ3111-K Best

【题目大意】

给出v[]和w[]，求的最大值。

【思路】

二分s(S)的值，可变形为s(S)*Σw>=Σv，所以只需要把求出x*w[i]-v[i]，看看前k个的和是否大于等于0，大于等于0就满足条件。

由于进度非常高，注意二分的写法。

*原本在check(mid)=1之后会存下ansqueue，然后再输出，就wa了。然而改成直接输出最后一次check的序列（不管返回是0还是1）。不明白为什么。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=100000+50;
 7 const double eps=1.0e-6;
 8 int n,k,v[MAXN],w[MAXN];
 9 int ansqueue[MAXN];
10 struct node
11 {
12     double rem;
13     int id;
14     bool operator < (const node &x) const
15     {
16         return (rem>x.rem);
17     }
18 };
19 node queue[MAXN];
20 
21 int check(double x)
22 {
23     for (int i=1;i<=n;i++) 
24     {
25         queue[i].rem=v[i]-x*w[i];
26         queue[i].id=i;
27     }
28     sort(queue+1,queue+n+1);
29     double sum=0;
30     for (int i=1;i<=k;i++) sum+=queue[i].rem;
31     if (sum>=0.0) return 1;
32         else return 0;
33 }
34 
35 void solve()
36 {
37     for (int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
38     double lb=0.0,ub=0x3f3f3f3f;
39     while (ub-lb>eps)
40     {
41         double mid=(lb+ub)/2;
42         if (check(mid)) lb=mid;
43             else ub=mid;
44     }
45     for (int i=1;i<=k;i++)
46     {
47         printf("%d",queue[i].id);
48         if (i!=k) cout<<' ';
49     }
50     /*我原本在check(mid)=1之后会存下ansqueue，然后再输出，就wa了。
51      然而改成直接输出最后一次check的序列（不管返回是0还是1）。不明白为什么。*/ 
52     cout<<endl;
53 }
54 
55 int main()
56 {
57     while (scanf("%d%d",&n,&k)!=EOF) solve();
58     return 0;
59 }