| ps | |
|---|---|
| 링크 | acmicpc.net/… |
| 출처 | BOJ |
| 문제 번호 | 15459 |
| 문제명 | Haybale Feast |
| 레벨 | 골드 1 |
| 분류 |
투 포인터, 우선순위 큐, 이분탐색 |
| 시간복잡도 | O(nlogn) |
| 인풋사이즈 | n<=100,000 |
| 사용한 언어 | Python |
| 제출기록 | 47084KB / 264ms |
| 최고기록 | 264ms |
| 해결날짜 | 2022/06/29 |
"""Solution code for "BOJ 15459. Haybale Feast".
- Problem link: https://www.acmicpc.net/problem/15459
- Solution link: http://www.teferi.net/ps/problems/boj/15459
Tags: [Two pointer] [Monotone queue]
"""
import collections
import sys
INF = float('inf')
def main():
N, M = [int(x) for x in sys.stdin.readline().split()]
F_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
left, right = iter(F_and_S), iter(F_and_S)
tot_flavor = 0
spiciness_deq = collections.deque()
answer = INF
while True:
if tot_flavor < M:
try:
f, s = next(right)
except StopIteration:
break
tot_flavor += f
while spiciness_deq and spiciness_deq[-1] < s:
spiciness_deq.pop()
spiciness_deq.append(s)
else:
answer = min(answer, spiciness_deq[0])
f, s = next(left)
tot_flavor -= f
if s == spiciness_deq[0]:
spiciness_deq.popleft()
print(answer)
if __name__ == '__main__':
main()
"""Solution code for "BOJ 15459. Haybale Feast".
- Problem link: https://www.acmicpc.net/problem/15459
- Solution link: http://www.teferi.net/ps/problems/boj/15459
Tags: [Two pointer] [Priority queue]
"""
import sys
from teflib import priorityqueue
INF = float('inf')
def main():
N, M = [int(x) for x in sys.stdin.readline().split()]
F_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
spiciness_heap = priorityqueue.UpdatableHeap()
left, right = iter(F_and_S), iter(F_and_S)
tot_flavor = 0
answer = INF
while True:
if tot_flavor < M:
try:
f, s = next(right)
except StopIteration:
break
tot_flavor += f
spiciness_heap.push(-s)
else:
answer = min(answer, -spiciness_heap.top())
f, s = next(left)
tot_flavor -= f
spiciness_heap.delete(-s)
print(answer)
if __name__ == '__main__':
main()
"""Solution code for "BOJ 15459. Haybale Feast".
- Problem link: https://www.acmicpc.net/problem/15459
- Solution link: http://www.teferi.net/ps/problems/boj/15459
Tags: [Disjoint set]
"""
import operator
import sys
from teflib import disjointset
def main():
N, M = [int(x) for x in sys.stdin.readline().split()]
F, S = zip(
*([int(x) for x in sys.stdin.readline().split()] for _ in range(N)))
dsu = disjointset.DisjointSet(N)
flavor_by_set = list(F)
for i, S_i in sorted(enumerate(S), key=operator.itemgetter(1)):
flavor_cur = F[i]
if i > 0 and S[i - 1] <= S_i:
flavor_left = flavor_by_set[dsu.find(i - 1)]
merged_set = dsu.union(i - 1, i)
flavor_cur = flavor_by_set[merged_set] = flavor_cur + flavor_left
if i + 1 < N and S[i + 1] <= S_i:
flavor_right = flavor_by_set[dsu.find(i + 1)]
merged_set = dsu.union(i + 1, i)
flavor_cur = flavor_by_set[merged_set] = flavor_cur + flavor_right
if flavor_cur >= M:
print(S_i)
break
if __name__ == '__main__':
main()
"""Solution code for "BOJ 15459. Haybale Feast".
- Problem link: https://www.acmicpc.net/problem/15459
- Solution link: http://www.teferi.net/ps/problems/boj/15459
Tags: [Binary search]
"""
import bisect
import sys
def main():
def is_valid(s):
f_sum = 0
for f_i, s_i in F_and_S:
if s_i > s:
f_sum = 0
else:
f_sum += f_i
if f_sum >= M:
return True
return False
N, M = [int(x) for x in sys.stdin.readline().split()]
F_and_S = [[int(x) for x in sys.stdin.readline().split()] for _ in range(N)]
s_sorted = sorted(set(s for f, s in F_and_S))
min_s_ind = bisect.bisect_left(s_sorted, True, key=is_valid)
print(s_sorted[min_s_ind])
if __name__ == '__main__':
main()