POJ 3111 K Best（二分答案）

【题目大意】

　　选取k个物品，最大化sum(ai)/sum(bi)

【题解】

　　如果答案是x，那么有sigma(a)>=sigma(b*x)
　　至于选取，就可以根据a-b*x排序，贪心选取即可。
　　对于输出物品的id，因为在不断逼近结果的过程中，排序的结果也不断在调整
　　所以我们最后的得到的排序结果的前k个就是答案。

【代码】

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=101000;

struct data{int a,b,id;}p[N];

int n,k,ans[N];

double m;

bool cmp(data a,data b){return a.a-m*a.b>b.a-m*b.b;}

bool check(double x){

    m=x;

    sort(p+1,p+n+1,cmp);

    double tot_v=0,tot_w=0;

    for(int i=1;i<=k;i++){tot_v+=p[i].a;tot_w+=p[i].b;}

    return tot_v/tot_w>x;

}

int main(){

    while(~scanf("%d%d",&n,&k)){

    	double l=0,r=0;

        for(int i=1;i<=n;i++)scanf("%d%d",&p[i].a,&p[i].b),p[i].id=i,r=max(r,(double)p[i].a/p[i].b);

        for(int i=1;i<=100;i++){

            double mid=(l+r)/2;

            if(check(mid))l=mid;

            else r=mid;

        }for(int i=1;i<=k;i++)ans[i]=p[i].id;

		sort(ans+1,ans+k+1);

		for(int i=1;i<k;i++)printf("%d ",ans[i]);

        printf("%d\n",ans[k]);

    }return 0;

}

秒客网

POJ 3111 K Best（二分答案）

相关文章