本文共 1110 字，大约阅读时间需要 3 分钟。

最大化$\frac{\sum t_i}{\sum w_i}$

令$r=\frac{\sum t_i}{\sum w_i}$

构造函数$f(r)=\sum t_i-r\ast \sum w_i$

对于不同的选取奶牛方案,对应直线各不相同,但斜率都是负数

且每条直线与$x$轴的交点就是答案,现在就是找出最大的答案

若二分一个$mid$作直线$x=mid$交于上述直线各个点

若存在交点的$y$左边大于零,说明最大值还在右边

否则,最大值在左边

所以,选择一个点的权值相当于$t_i-mid\ast w_i$

但是现在有$W$的限制,怎么办呢?

那就把$w$看作体积,$t_i-mid\ast w_i$看作价值

做一遍$01$背包即可

但是注意,当体积超过$W$时也去更新$W$

不然空间爆掉了

#include 
   
    using namespace std;#define int long longconst int maxn=3e5+10; int n,W,dp[20009],w[maxn],t[maxn];bool isok(int mid){
   	int inf = 1e18;	for(int i=0;i<=W;i++)	dp[i]=-inf;	dp[0]=0;	for(int i=1;i<=n;i++)	for(int j=W;j>=0;j--)		if( dp[j]!=-inf )		{
   			int v=min( W,j+w[i] );			dp[v]=max(dp[v],dp[j]+t[i]-w[i]*mid );		}	return dp[W]>=0;}signed main(){
   	cin >> n >> W;	for(int i=1;i<=n;i++)	{
   		scanf("%lld%lld",&w[i],&t[i]);		t[i]*=1000;		}	int l=0,r=1000000,ans=0;	while( r>=l )	{
   		int mid = l+r>>1;		if( isok(mid) )	l=mid+1,ans=mid;		else	r=mid-1;	}	cout << ans;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/109392812 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！