AcWing 4656. 技能升级
原题链接
困难
作者:
Nan97
,
2023-01-10 09:57:36
,
所有人可见
,
阅读 162
好难的二分~
n, m = map(int, input().split())
a, b = [0] * n, [0] * n
for i in range(n):
a[i], b[i] = map(int, input().split())
def chk(low):
tot = 0
for x, y in zip(a, b):
if x > low:
tot += (x - low + y - 1) // y
return tot <= m
l, r = 0, max(a)
while l < r:
mid = l + r >> 1
if chk(mid):
r = mid
else:
l = mid + 1
def calc(low):
ans, tot, ct = 0, 0, 0
for x, y in zip(a, b):
if x > low:
Time = (x - low + y - 1) // y
ans += (x + x - (Time - 1) * y) * Time // 2
tot += Time
if x - Time * y == low:
ct += 1
elif x == low:
ct += 1
while tot < m and ct:
tot += 1
ct -= 1
ans += low
return ans
print(calc(l))
阅,希望别卖弱
阅
。