题解 | 达牛秀-牛客假日团队赛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
全部评论

相关推荐

过往烟沉:我说什么来着,java就业面就是广!
点赞 评论 收藏
分享
头像
10-22 19:18
上海大学 后端
jopajhhdjwnqk:水印都叠杀人书了
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务