1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
(step4)C. Pair Selection(CF).py 1.26 KB
一键复制 编辑 原始数据 按行查看 历史
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/9
# @File : (step4)C. Pair Selection(CF).py
# https://codeforces.com/edu/course/2/lesson/6/4/practice/contest/285069/problem/C
"""
Given n pairs of positive integers (a1,b1),(a2,b2),…,(an,bn). Select k (1≤k≤n) of them i1,i2,…,ik
so that the ratio ai1+ai2+⋯+aik/bi1+bi2+⋯+bik is maximum possible.
"""
def check(mid):
pre = []
for i in range(n):
pre.append(char[i][0] - mid * char[i][1])
pre.sort(reverse=True)
tmp = sum(pre[0:k])
if (tmp >= 0):
return True
return False
def bi():
l = -1
r = 1000000
for _ in range(100):
mid = (l + r) / 2
if (check(mid)):
l = mid
else:
r = mid
return l
if __name__ == "__main__":
"""
最大化平均值 C. Pair Selection
0,二分平均数,找最大肯定是左二分。
1,推导公式(移项)
2,转化问题
3,排序,因为只要找到比0大的,存在就行 , 所以就尽可能找最大的K个。
"""
n, k = map(int, input().split())
char = []
for _ in range(n):
a, b = map(int, input().split())
char.append((a, b))
print(bi())
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/bensonrachel/atcoder_algorithm.git
git@gitee.com:bensonrachel/atcoder_algorithm.git
bensonrachel
atcoder_algorithm
Atcoder_algorithm
master

搜索帮助