首页 > 代码库 > POJ 3111 K Best（二分答案）
POJ 3111 K Best（二分答案）
【题目链接】 http://poj.org/problem?id=3111
【题目大意】
选取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（二分答案）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。