题解 | 达牛秀-牛客假日团队赛4D题
D-达牛秀_牛客假日团队赛4
https://ac.nowcoder.com/acm/contest/947/D
题目描述
Farmer John要带着他的
头奶牛，方便起见编号为
，到农业展览会上去，参加每年的达牛秀！他的第ii头奶牛重量为
，才艺水平为
，两者都是整数。
在到达时，Farmer John就被今年达牛秀的新规则吓到了：
（一）参加比赛的一组奶牛必须总重量至少为（这是为了确保是强大的队伍在比赛，而不仅是强大的某头奶牛），并且
（二）总才艺值与总重量的比值最大的一组获得胜利。
FJ注意到他的所有奶牛的总重量不小于
，所以他能够派出符合规则（一）的队伍。帮助他确定这样的队伍中能够达到的最佳的才艺与重量的比值。
输入描述:
输入的第一行包含和
。下面
和
描述了一头奶牛。
输出描述:
请求出Farmer用一组总重量最少为W的奶牛最大可能达到的总才艺值与总重量的比值。如果你的答案是AA，输出1000A向下取整的值，以使得输出是整数（当问题中的数不是一个整数的时候，向下取整操作在向下舍入到整数的时候去除所有小数部分）。
示例1
输入
3 15
20 21
10 11
30 31
输出
1066
说明
在这个例子中，总体来看最佳的才艺与重量的比值应该是仅用一头才艺值为11、重量为10的奶牛，但是由于我们需要至少15单位的重量，最优解最终为使用这头奶牛加上才艺值为21、重量为20的奶牛。这样的话才艺与重量的比值为，乘以1000向下取整之后得到1066。
解答
解法：这题改编自最大化平均值，但却是贪心->01背包问题
我们需要找到当前重量的最大
看其是否
递推关系:
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=253;
const double INF = 0x3f3f3f3f;
int w[N], v[N];
double p[N], dp[1003];
int n,W;
const double eps=1e-8;
bool C(double x)
{
for(int i=0; i<n; i++)
{
p[i]=(double)(v[i]-x*w[i]);
}
for(int i=0; i<=W; i++) dp[i]=-INF;
dp[0]=0; //重量为0时的∑p[i]=0
for(int i=0; i<n; i++)
{
for(int j=W; j>=0; j--)
{
if(W<=w[i]+j) dp[W]=max(dp[W],dp[j]+p[i]);
else if(W>=w[i]+j) dp[w[i]+j]=max(dp[w[i]+j],dp[j]+p[i]);
}
}
return dp[W]>=0;
}
int main()
{
double ans;
cin>>n>>W;
for(int i=0; i<n; i++) cin>>w[i]>>v[i];
double l=0, r=3000;
while(r-l>eps)
{
double mid=(l+r)/2;
if(C(mid)) l=mid, ans=mid;
else r=mid;
}
cout<<(int)(ans*1000.0)<<endl;
return 0;
} 来源：Hcacai
