最大化平均值(二分搜索)

最新推荐文章于 2024-03-02 17:05:21 发布

OFShare

最新推荐文章于 2024-03-02 17:05:21 发布

阅读量418

点赞数

分类专栏： ACM-二分搜索

本文链接：https://blog.csdn.net/Cui_csdn/article/details/72931962

版权

ACM-二分搜索专栏收录该内容

4 篇文章

订阅专栏

//有n个物品的重量和价值分别是Wi和Vi.从中选出k个物品使得单位重量的价值最大
bool judge(double mid)
{
	vector<double> vec;
	for(int i=0;i<N;++i)
		vec.push_back(v[i]-w[i]*mid);
	sort(vec.begin(),vec.end());
	double sum=0;
	for(int i=0;i<K;++i)
	{
		sum+=vec[N-i-1];
	}
	return sum>=0;
}
void solve()
{
	double a=0,b=INF;
	for(int i=0;i<100;++i)
	{
		double mid=a+(b-a)/2;
		if(judge(mid))
			a=mid;
		else
			b=mid;
	}
}