A、gpa （01分数规划）

A、gpa （01分数规划）

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≤ n≤ 105 0≤ k < n 1≤ s[i],c[i] ≤ 103    示例 1 输入 3 1 1 2 3 3 2 1 输出 2.33333333333

基本的01分数规划题。

退一下公式就行。

代码：

#include using namespace std;#define ll long longconst int maxn=1e5+10;double s[maxn],c[maxn];double d[maxn];bool pan(int n,int k,double x){ for(int i=1;i<=n;i++) { d[i]=s[i]*(c[i]-x); } sort(d+1,d+1+n); double sum=0; for(int i=k+1;i<=n;i++) { sum+=d[i]; } return sum>=0;}int main(){ int n,k; scanf("%d%d",&n,&k); for(int i=1; i<=n; i++) { scanf("%lf",&s[i]); } for(int i=1; i<=n; i++) { scanf("%lf",&c[i]); } double l=0,r=1010; while(r-l>1e-8) { double mid=(l+r)/2; if(pan(n,k,mid)) { l=mid; } else r=mid; } printf("%.11lf\n",l); return 0;}/*3 11 2 33 2 1*/

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。