1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
(step5)C. K-th Sum (CF).py 1.18 KB
一键复制 编辑 原始数据 按行查看 历史
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/6
# @File : (step5)C. K-th Sum (CF).py
# https://codeforces.com/edu/course/2/lesson/6/5/practice/contest/285084/problem/C
def bi_common(n,x):#从1开始
l = 0
r = n+1
while(l+1<r):
mid = (l+r)//2
if(arr2[mid]<=x-1):#从1开始的一般这样就可以把等号写在这里,就是写x-1,而不是x,这样就可以统一返回l
l = mid
else:
r = mid
return l
def check(n,mid):
cnt = 0
for i in arr1:
cnt += bi_common(n,mid-i)
return cnt
def bi(n,k):
l = 0
r = 2*10**9 +1
while(l+1<r):
mid = (l+r)//2
if(check(n,mid)<=k-1):
l = mid
else:
r = mid
return l
if __name__ == "__main__":
n,k = map(int ,input().split())
arr1 = [int(i) for i in input().split()]
arr2 = [int(i) for i in input().split()]
arr1.sort()
arr2.sort()
res = bi(n,k)
print(res)
"""
O(n*logn*logn),check为n*logn。
bi_common函数也是为了计算出有多少个小于当前的和的,也是包括这个和
也是从1开始的k-th,跟B题是一样的。
"""
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/bensonrachel/atcoder_algorithm.git
git@gitee.com:bensonrachel/atcoder_algorithm.git
bensonrachel
atcoder_algorithm
Atcoder_algorithm
master

搜索帮助

371d5123 14472233 46e8bd33 14472233