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; }

轉載于:https://www.cnblogs.com/YYC-0304/p/10458955.html

總結

以上是生活随笔為你收集整理的淬炼神体的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。