首页 > 代码库 > poj2976(01分数规划)
poj2976(01分数规划)
题目连接:http://poj.org/problem?id=2976
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int maxn=1010; 6 double a[maxn],b[maxn],d[maxn]; 7 int n,k; 8 bool check(double x) 9 { 10 double ans=0; 11 for(int i=0;i<n;i++) 12 d[i]=a[i]-x*b[i]; 13 sort(d,d+n); 14 for(int i=k;i<n;i++) 15 ans+=d[i]; 16 return ans>0; 17 } 18 19 int main() 20 { 21 while(scanf("%d%d",&n,&k)&&(n||k)) 22 { 23 for(int i=0;i<n;i++) 24 scanf("%lf",&a[i]); 25 for(int i=0;i<n;i++) 26 scanf("%lf",&b[i]); 27 double l=0,r=1.0,mid; 28 while(r-l>1e-7) 29 { 30 mid=(l+r)*1.0/2; 31 if(check(mid)) l=mid; 32 else r=mid; 33 } 34 printf("%.0f\n",mid*100); 35 } 36 }
poj2976(01分数规划)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。