kk编程446. 刷题者

Question

**编程上共有n题，实在是太多了估计没人能做完。做对第i题会得到si分，但需要花费ti小时。你作为一个聪明的刷题者，希望能完成其中的k题，该如何挑选才能使每小时的平均得分最高呢？
输入格式
输入第一行为正整数n和k，第二行共n个正整数代表每个si，第三行共n个正整数代表每个ti。k<=n<=100000，si,ti<=100。
输出格式
输出最高的每小时平均得分，保留两位小数。
输入样例#1:
3 2
2 3 1
2 5 2
输出样例#1:
0.75

Answer 1

#include<bits/stdc++.h>
using namespace std;
const int N=100009;
const double ERR=0.000001;
double s[N],t[N],z[N];
int n,k;
bool OK(double x){
for(int i=0;i<n;i++)
z[i]=s[i]-x*t[i];
sort(z,z+n);
double sum=0;
for(int i=n-k;i<n;i++)
sum+=z[i];
return sum>=0;
}
int main(){
cin>>n>>k;
for(int i=0;i<n;i++) cin>>s[i];
for(int i=0;i<n;i++) cin>>t[i];
double maxs=*max_element(s,s+n);
double mint=min_element(t,t+n);
double l=0,r=maxs/mint,ans=0;
while(r-l>ERR){
double mid=l+(r-l)/2;
if(OK(mid)) ans=l=mid;
else r=mid;
}
cout<<fixed<<setprecision(2)<<ans1.000<<endl;;
return 0;
}