AcWing 3745. 牛的学术圈 I + 前缀和
原题链接
简单
作者:
SXWL
,
2024-03-05 17:52:46
,
所有人可见
,
阅读 19
N, L = map(int, input().split())
c = [0] + list(map(int, input().split()))
s = [0] * (int(1e5) + 2) # 存储不同引用次数的数量
l, r, num = 1, N, 0
while l < r:
s[c[l]] += 1
s[c[r]] += 1
if num < max(c[l], c[r]):
num = max(c[l], c[r])
l, r = l + 1, r - 1
if l == r:
s[c[l]] += 1
if num < max(c[l], c[r]):
num = max(c[l], c[r])
# 构造“前缀和”数组
for i in range(num, 0, -1):
s[i] += s[i + 1]
for i in range(N, 0, -1):
# 如果s[i]的大小满足则直接打印(即不需要考虑L),不满足的话再考虑L
if s[i] >= i or (s[i - 1] - s[i] >= i - s[i] and L >= i - s[i]):
print(i)
exit(0)
print(0)