AcWing 4656. 技能升级
原题链接
困难
作者:
Lebowski
,
2023-01-10 16:22:57
,
所有人可见
,
阅读 133
代码
#多路归并
'''
首先这道题的最朴素思想,由于每路技能升级就相当于递减的等差数列,我们可以把各路等差数列倒序排在一起找前m个最大的数;加起来肯定是答案
然后再去想优化;这个m是1e9,应该是nlogn复杂度可以解
然后我们分析,从大到小排序之后,会存在一个x值,使得前面 >= x的数的个数是>= m个的;>= x+1的数的个数是< m个的。
我们只要通过二分0,1e6(每段等差数列的区间)找到这个x的值,使得存在这样一个x作为每路等差数列的下界;如果有这么一个x值我们可以遍历每路等差数列
用公式 (a-x/b + 1)求一下每路满足的个数然后把每路的个数加起来算一个cnt,cnt >= m 就行了
上面这个逻辑是可以用二分去做的,if check(mid)的逻辑是o(n)的,所以整体是nlogn的
接着知道这个x之后,就可以用等差数列的性质去做了
'''
n,m = map(int, input().split()) #n个等差数列,m是前m个数
a = [0] * n
b = [0] * n
for i in range(n):
a[i], b[i] = map(int, input().split())
def check(mid):
res = 0
for i in range(n): #遍历每一路等差数列
if a[i] >= mid:
res += (a[i] - mid) // b[i] + 1 #每一路有多少项大于等于mid的,加在一起
return res
def func(n,m):
l, r = 0, 1000000 #二分的边界取决于a b 即等差数列给的数
while (l < r):
mid = (l+r+1) // 2
if check(mid) >= m: l = mid #即存在一个x,使得>=x的数的个数是 >=m个的
else: r = mid - 1
cnt, res = 0, 0
for i in range(n):
if a[i] >= l:
c = (a[i] - l) // b[i] + 1 #项数
end = a[i] - (c-1) * b[i] #末项
cnt += c
res += (a[i] + end) * c // 2
return (res - (cnt - m) * l) #因为 我们二分出来的数可以重复嘛,我们按照它为下界各路归并出来的数可能大于m项
print(func(n,m))