A gpa（0-1分数规划）

题目描述
Kanade selected n courses in the university. The academic credit of the i-th course is s[i] and the score of the i-th course is c[i].
At the university where she attended, the final score of her is

Now she can delete at most k courses and she want to know what the highest final score that can get.

输入描述:
The first line has two positive integers n,k

The second line has n positive integers s[i]

The third line has n positive integers c[i]
输出描述:
Output the highest final score, your answer is correct if and only if the absolute error with the standard answer is no more than 10-5
示例1
输入
复制
3 1
1 2 3
3 2 1
输出
复制
2.33333333333
说明
Delete the third course and the final score is
备注:
1≤ n≤ 105
0≤ k < n
1≤ s[i],c[i] ≤ 103

0-1分数规划
r=(t1*x1+t2*x2+…+tn*xn)/(c1*x1+c2*x2+…+cn*xn)
给定t[1-n],c[1-n]，求x[1-n]使得sigma（xi）=k且r最大（小）
为了让r最大，设z(r)= (t1*x1+ .. +tn*xn)-r * (c1*x1+..+cn*xn)
假设r的最优值为R，则：
z(r)<0,当且仅当r>R;
z(r)=0,当且仅当r=R;
z(r)>0,当且仅当r

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
#define LL long longusing namespace std;
const int maxn=100005;
int n,k;
int s[maxn],c[maxn];
double f[maxn];int check(double m)
{for(int i=0;idouble ans=0;for(int i=k;ireturn ans>=0;
}int main()
{while(scanf("%d%d",&n,&k)==2){for(int i=0;iscanf("%d",&s[i]);}for(int i=0;iscanf("%d",&c[i]);}for(int i=0;iint t=s[i];s[i]=s[i]*c[i];c[i]=t;}double l=0,r=inf;while(r-l>0.000001){double mid=(l+r)/2;if(check(mid)){l=mid;}else{r=mid;}}printf("%.11f\n",l);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！