首页 > 代码库 > POJ 3111 K Best
POJ 3111 K Best
传送门:http://poj.org/problem?id=3111
这也是01规划问题,
解题思路见http://www.cnblogs.com/IKnowYou0/p/6696805.html
实现代码:
#include <iostream> #include <cstdio> #include <algorithm> using namespace std; const int MAXN=100005; const double eps=1e-6; double a[MAXN],b[MAXN],d[MAXN]; int N,K; bool cmp1(double x,double y){ return x>y; } bool calc(double r){ for(int i=0;i<N;i++) d[i]=a[i]-b[i]*r; double sum=0; sort(d,d+N,cmp1); for(int i=0;i<K;i++) sum+=d[i]; return sum<=0.0; } struct Node{ int id; double d; }node[MAXN]; bool cmp2(Node x,Node y){ return x.d>y.d; } bool cmp3(Node x,Node y){ return x.id<y.id; } int main(){ cin>>N>>K; for(int i=0;i<N;i++) scanf("%lf%lf",&a[i],&b[i]); double l=0.0,r=100000000.0; while(r-l>eps){ //这儿的精度要求有点高 double mid=(l+r)/2.0; if(calc(mid)) r=mid; else l=mid; } for(int i=0;i<N;i++){ node[i].id=i+1; node[i].d=a[i]-l*b[i]; } sort(node,node+N,cmp2); for(int i=0;i<K;i++) printf("%d%c",node[i].id,i+1==K?‘\n‘:‘ ‘); return 0; }
POJ 3111 K Best
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。