网站模板 登陆,住房住房和城乡建设部网站首页,洪洞网站建设,北京网页设计公司兴田德润简介链接#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源#xff1a;牛客网
题目描述
小咪是一个土豪手办狂魔#xff0c;这次他去了一家店#xff0c;发现了好多好多#xff08;n个#xff09;手办#xff0c;但他是一个很怪的人#xff0c;每次只想买k个手办登录—专业IT笔试面试备考平台_牛客网 来源牛客网
题目描述
小咪是一个土豪手办狂魔这次他去了一家店发现了好多好多n个手办但他是一个很怪的人每次只想买k个手办而且他要让他花的每一分钱都物超所值即买下来的东西的总价值/总花费max。请你来看看他会买哪些东西吧。
输入描述: 多组数据。
第一行一个整数T为数据组数。
接下来有T组数据。
对于每组数据第一行两个正整数nk如题。
接下来n行每行有两个正整数civi。分别为手办的花费和它对于小咪的价值。
输出描述:
对于每组数据输出一个数即能得到的总价值/总花费的最大值。精确至整数。 #includebits/stdc.h
typedef long long ll;
using namespace std;
ll n,k;
struct fx{ll c,v;double y;
};
fx a[10003];
ll check(double x)
{for(ll i1;in;i){a[i].ya[i].c*1.0-x*a[i].v;}sort(a1,a1n,[](fx p,fx q){return p.yq.y;});double f0;for(ll i1;ik;i){fa[i].y;}return f0;
}
void solve()
{cinnk;for(ll i1;in;i){cina[i].va[i].c;}double l0;double r0;for(ll i1;in;i)ra[i].c;for(ll i0;i100;i){double midl(r-l)/2;if(check(mid))rmid;else lmid;}coutll(l)\n;
}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t1;cint;while(t--)solve();return 0;
}
