wyh的物品

wyh的物品

https://ac.nowcoder.com/acm/problem/15446

思路

这题考虑二分答案,既选k个物品总价值与总重量的比值

价值 图片说明 等式两边同时乘图片说明可以得到图片说明

我们要所选的k个总单位价值最大,即要选的数量中图片说明 最大,所以二分的check函数对图片说明按降序排列,算出前k个之和是否大于0,大于0就说明当前单位价值可以到达,反之不能

代码

#pragma GCC target("avx,sse2,sse3,sse4,popcnt")
#pragma GCC optimize("O2,O3,Ofast,inline,unroll-all-loops,-ffast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
#define pb push_back
#define pll pair<ll,ll>
#define INF 0x3f3f3f3f
const int mod = 100000000;
const int maxn = 100005;
inline ll read(){
    ll s = 0, w = 1; char ch = getchar();
    while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }
    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
    return s * w;
}
struct node{
    int a,b;
    double c;
    bool operator < (const node & A) const {
        return c > A.c;
    }
}q[100005];
int n,k;
bool check(double x){
    for(int i = 0 ; i < n ; ++i) q[i].c = q[i].b - q[i].a*x;
    sort(q,q+n);
    double ans = 0;
    for(int i = 0 ; i < k ; ++i){
        ans += q[i].c;
    }
    return ans >= 0;
}
int main(){
    int t = read();
    while(t--){
        n = read();k = read();
        for(int i = 0 ; i < n ; ++i){
            q[i].a = read();
            q[i].b = read();
        }
        double l = 0,r = 1e9,ans;
        for(int i = 0 ; i < 100 ; ++i){
            double mid = (l + r) / 2;
            if(check(mid)) ans = mid,l = mid;
            else r = mid;
        }
        printf("%.2f\n",ans);
    }
}
算法竞赛入门课习题 文章被收录于专栏

0

全部评论

相关推荐

07-11 22:27
中南大学 Java
程序员牛肉:学历的话没问题。但是没问题的也就只有学历了。 其实你的整体架构是正确的,博客接着干。但是项目有点过于简单了。从后端的角度上讲,你这也就是刚入门的水平,所以肯定约面试够呛。 如果你要应聘后端岗位,那你第一个项目竟然是仿写操作系统。这个你要面试官咋问你。你一定要记住一点,你简历上写的所有的东西,都是为了证明你有能力胜任当前的岗位,而不是为了证明你自己会什么。 如果你只是浅浅的做几个项目,描述也都是烂大街。技术点也都是各种混水类的配置类需求,那你就不要幻想自己能走多远。一定要保持思考,保持学习。
点赞 评论 收藏
分享
认真搞学习:28小登的建议,投算法岗不要写什么物理竞赛,互联网+,多写点项目,用什么算法做了什么。还有本科算法是不可能的开发你这个也没有项目啊
点赞 评论 收藏
分享
评论
8
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务