购物网站开发周期,o2o平台排名,青岛互联网公司排名,网页视觉设计流程正题 题目大意 nnn个东西#xff0c;有ai,bia_i,b_iai,bi。选择kkk个#xff0c;使得∑ai/∑bi\sum a_i/\sum b_i∑ai/∑bi最大。 解题思路 ∑ai/∑bik\sum a_i/\sum b_ik∑ai/∑bik ∑ai/∑bi/k1\sum a_i/\sum b_i/k1∑ai/∑bi/k1 ∑ai/k∑bi\sum a_i/k\sum…正题 题目大意
nnn个东西有ai,bia_i,b_iai,bi。选择kkk个使得∑ai/∑bi\sum a_i/\sum b_i∑ai/∑bi最大。 解题思路
∑ai/∑bik\sum a_i/\sum b_ik∑ai/∑bik ∑ai/∑bi/k1\sum a_i/\sum b_i/k1∑ai/∑bi/k1 ∑ai/k∑bi\sum a_i/k\sum b_i∑ai/k∑bi 那么 ∑(ai/k−bi)gt;0\sum (a_i/k-b_i)gt;0∑(ai/k−bi)0 然后二分kkk就好了 然后每次选取ai/k−bia_i/k-b_iai/k−bi最大的kkk个就好了 codecodecode
#includecstdio
#includealgorithm
using namespace std;
const int N100010;
int n,k;
double l,r,a[N],b[N],c[N];
bool check(double ks)
{double ans0;for(int i1;in;i){c[i]a[i]/ks-b[i];}sort(c1,c1n);for(int in;in-k1;i--)ansc[i];return (ans0);
}
int main()
{//freopen(data.in,r,stdin);//freopen(data.out,w,stdout);scanf(%d%d,n,k);for(int i1;in;i)scanf(%lf,a[i]);for(int j1;jn;j)scanf(%lf,b[j]);l1e-4;r20000;while(r-l1e-6){double mid(lr)/2;if(check(mid)) lmid;else rmid;}printf(%0.3lf,l);
}
