本文主要是介绍淬炼神体，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Description
王仙女将你提供的答案填在《葵花宝典》上，突然，宝典发出耀眼的白光，一股强大的吸力瞬间将仙女吸入宝典中。
一阵眩晕过后，仙女发现自己来到了一个浮岛上，四周的半空中也有许多大小不一的浮岛，他抬头一看，空中浮现着这样一句话：欲要成神，必先成就神体。每座浮岛都有一定的淬炼肉体的功效，但你只能选择恰好K座来淬炼你的肉体。最终你的神体有多强，就看你的造化了。
仙女看了看手中的宝典，发现上面浮现着这些浮岛的信息，每座浮岛上有两个数字。仙女研究了一会儿终于明白了，原来，每来到一座浮岛，你就会由这座岛上的神雷淬炼肉体，得到a点淬炼值，但是这种淬炼方法对身体又有一定的伤害，于是你会受到b点损伤值。而最后你的神体强度恰好为你得到的淬炼值之和与你受到的损伤值之和的比值。即神体强度=(∑a)/(∑b)。同时，你不能选择一座浮岛两次。你不必担心仙女如何到达其它的岛，宝典拥有将他传送至任何一座岛的能力。
现在，仙女想知道，他有可能淬炼出的神体的最大强度是多少。他把这个问题交给了未来的你作为刚刚帮助过他的答谢。
Input
第一行包含两个整数N，K，分别表示浮岛的数量(不包括仙女所在的浮岛)和仙女可以选择的浮岛数，浮岛的编号为1~N
第二行包含N个整数，第i个数为编号为i的浮岛的淬炼值a
第二行包含N个整数，第i个数为编号为i的浮岛的损伤值b
Output
一个实数，为仙女有可能淬炼出的神体的最大强度，保留三位小数。
Sample Input
3 2
5 7 1
4 3 2
Sample Output
1.714
Data Constraint
对于30%的数据，2≤K≤N≤10，1≤a，b≤5
对于100%的数据，2≤K≤N≤100000，1≤a，b≤1000
.
.
.
.
.
.
分析
如果有
(∑a)/(∑b)=mid
那么
(∑a)=mid*(∑b)
可得
(∑a)-mid*(∑b)=0
所以
∑(a-mid*b)=0
综上
mid为答案
我们可以二分这个mid
设w[i]=a[i]-mid*b[i]
排序并求和前k个==sum
如果sum>=0，那么这个mid合法，我们就继续二分，直至最优解。
.
.
.
.
.
程序：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;int n,k;
double a[100010],b[100010],w[100010];void kp(int l,int r)
{if (l>r) return;int i=l,j=r;double mid=w[(l+r)/2];do{while (w[i]>mid) i++;while (w[j]<mid) j--;if (i<=j){w[0]=w[i];w[i]=w[j];w[j]=w[0];i++;j--;}} while (i<=j);kp(l,j);kp(i,r);
}int main()
{scanf("%d%d",&n,&k);;for (int i=1;i<=n;i++)scanf("%lf",&a[i]);for (int i=1;i<=n;i++) scanf("%lf",&b[i]);double bz=0;for (int i=1;i<=n;i++)if (a[i]/b[i]>bz) bz=a[i]/b[i];double l=0,r=bz,flag=0.0001,mid;while (fabs(r-l)>=flag){mid=(l+r+flag)/2;memset(w,0,sizeof(w));for (int i=1;i<=n;i++)w[i]=a[i]-b[i]*mid;kp(1,n);double tj=0;for (int i=1;i<=k;i++)tj+=w[i];if (tj>=0) l=mid; else r=mid-flag;}printf("%0.3lf",mid);return 0;
}
这篇关于淬炼神体的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
