首页 > 【模板】01分数规划
开通博客写题解
头像 Z_L_G
发表于 2025-03-19 23:01:15
定义 有n个物品，每个物品有价值和消耗，从其中拿k个，希望使得 ∑价值/∑消耗 最大 方法 设最优解X=∑v/∑c，对式子做变形有∑v-X∑c=0，再变形有∑(v-Xc)=0 易发现这是一个单调式子，故考虑使用二分 二分X，每次计算当前X下的(v-Xc)，取前k个求∑(v-Xc)，如果小于0则 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”