2191. 卡牌
摘要
Title: 2191. 卡牌
Tag: 二分
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
2191. 卡牌
-
题意
略
-
思路
二分答案即可，检测二分时：
- 看m是否耗光
- 看b[i]是否能让加那么多
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69'''
Author: NEFU AB-IN
Date: 2023-05-24 19:49:37
FilePath: \LanQiao\2191\2191.py
LastEditTime: 2023-05-24 19:55:56
'''
# import
from sys import setrecursionlimit, stdin, stdout, exit
from collections import Counter, deque
from heapq import heapify, heappop, heappush, nlargest, nsmallest
from bisect import bisect_left, bisect_right
from datetime import datetime, timedelta
from string import ascii_lowercase, ascii_uppercase
from math import log, gcd, sqrt, fabs, ceil, floor
class sa:
def __init__(self, x, y):
self.x = x
self.y = y
def __lt__(self, a):
return self.x < a.x
# Final
N = int(2e5 + 10)
M = 20
INF = int(2e9)
# Define
setrecursionlimit(INF)
input = lambda: stdin.readline().rstrip("\r\n") # Remove when Mutiple data
read = lambda: map(int, input().split())
LTN = lambda x: ord(x.upper()) - 65 # A -> 0
NTL = lambda x: ascii_uppercase[x] # 0 -> A
# —————————————————————Division line ——————————————————————
a = [0] * N
b = [0] * N
def check(mid):
cnt = m
for i in range(1, n + 1):
if b[i] < mid - a[i]:
return False
if a[i] < mid:
cnt -= (mid - a[i])
if cnt < 0:
return False
return True
n, m = read()
a[1:] = read()
b[1:] = read()
l, r = min(a), max(a)
while l < r:
mid = (l + r + 1) >> 1
if check(mid):
l = mid
else:
r = mid - 1
print(r)