1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
C - Tsundoku.py 2.62 KB
一键复制 编辑 原始数据 按行查看 历史
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/7/11
# @File : 172 C - Tsundoku.py
import itertools
import bisect#可以查找一个数插入一个有序序列的位置,返回下标。
def bisearch(l,r,r_x,x,arr:list):#用二分实现bisect的功能
while (l + 1 < r):
mid = (r + l) // 2 # 1.
if arr[mid] < x: # 3.
l = mid
else:
r = mid
if(r <= r_x-1 and arr[r]==x):
return r + 1
else:
return r
def re(a:list,b:list,n,m,k):
x = bisearch(-1,n,n,k,a)
y = bisearch(-1,m,m,k,b)
#print(y)
res = 0
if(y-1 == -1):
print(x)
else:
z = 0
for i in range(y-1,-1,-1):
z = bisearch(z-1,x,x,k-b[i],a)#每次的二分找插入位置不用从整个小于等于K的前序序列找,因为是递增的,所以记录上一次到哪,然后从这个位置开始到小于等于K的前序序列的最后进行查找即可
#print(str(z)+"**")
res = max(res,z+i+1)
#print(res)
res = max(res,x)
print(res)
if __name__ == '__main__':
N, M, K = map(int, input().split())
rate_n = [int(i) for i in input().split()]
rate_m = [int(i) for i in input().split()]
acc_a = list(itertools.accumulate(rate_n))
acc_b = list(itertools.accumulate(rate_m))
re(acc_a,acc_b,N,M,K)
"""
1.使用贪心处理最上面的书肯定是不行的
2.两个桌子的地位是平等的,互换去解决也是OK的
3.方法:先求出两个数组的前缀和数组,获取小于等于K的前序序列(这一步想到了)错误想法:拿到A,B中更长的一个,再从短的开头开始累计可以加进去的,
这其实只是做了正确的方法中的一种情况。
正确方法:
A,B均为前缀和序列
接下来的思路就是:从其中一个序列的角度去,这里假设A,(用B也可以)
1)如果A的第一个数也比K大,所以就只能插在0这个位置,A序列说明一个也不能用
说明这个时候取B的小于等于K的前缀序列就行。
2)如果K不是插在队头(说明小于等于K的前序序列不为空),那么就从小于等于K的前序序列后面一个个减,第一次肯定减0个,看一下剩下的可以从B从头开始要几个,这种情况就是上面的说的做了正确的方法中的一种情况。
然后每减去一个比一次,更新比较大的res,最后A一个也不要(等于全部都从B里面拿),再与res做比较,最后输出这个最大值即可。计数的时候要小心
"""
"""
上面A,B互换也可以的,代码就是从B入手。
"""
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/bensonrachel/atcoder_algorithm.git
git@gitee.com:bensonrachel/atcoder_algorithm.git
bensonrachel
atcoder_algorithm
Atcoder_algorithm
master

搜索帮助