P6002 [USACO20JAN] Berry Picking S
2024-12-14
241214julyfunnoteswilliam工作P6002 [USACO20JAN] Berry Picking S所以有前 k / 2号元素都是一个相同值枚举这个值m，有三种情况最多能取出k个m，则前所有元素均为 m最多能取小于 k / 2 个 m，无解否则尽可能取多个 m，剩下部分取最大的即可._, k = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
for m in range(1, 1001):
num = 0
res = 0
rest = []
for x in a:
num += x // m
rest.append(x % m)
if num >= k:
res = m * k // 2
elif num >= k // 2:
res = (num - k // 2) * m + sum(sorted(rest, reverse=True)[:(k - num)])
ans = max(ans, res)
print(ans)Cow Frisbee S维护一个单调栈，每进入一个数 ai，就向前扫描直到遇见一个 s_top>ai，由于有 ai 挡着，所以之后的我们全部都看不见，此时最终答案加上 (i−stop+1)。from collections import deque
MAXN = int(1e6)
n = 0
ans = 0
a = [0] * (MAXN + 1)
s = deque()
n = int(input())
for i in range(1, n + 1):
a[i] = int(input())
for i in range(1, n + 1):
while s and a[s[-1]] < a[i]:
ans += i - s[-1] + 1
s.pop()
if s:
ans += i - s[-1] + 1
s.append(i)
print(ans)# [USACO19JAN] Icy Perimeter S冰淇淋的面积用dfs很好求只要算出每个联通块中'#'的个数即可难点在于求联通快的周长观察一下样例 发现周长就是每个'#'周围'.'或超过边界的方块个数解决这一问题后这道题几乎就是一道dfs裸题