사용자 도구

사이트 도구


ps:problems:boj:19584

난개발

ps
링크acmicpc.net/…
출처BOJ
문제 번호19584
문제명난개발
레벨골드 3
분류

스위핑

시간복잡도O(nlogn)
인풋사이즈n<=2*10^5
사용한 언어Python 3.11
제출기록85156KB / 1092ms
최고기록924ms
해결날짜2023/08/21

풀이

  • 뭔가 그래프 문제처럼도 보이고 기하 문제처럼도 보이게 포장을 살짝 해놓았는데, 포장을 풀고 나면 결국 가장 인터벌이 많이 겹치는 점을 찾는 문제이다. 장소들의 x좌표는 문제를 푸는데 있어서는 무시해도 되고 y좌표만을 가지고서 1차원 배열로 생각하면 된다.
  • 각 도로들은, 도로가 연결하는 두 장소의 번호를 좌표로 변환하고 거기에서 y좌표값만들을 취하면, 가중치가 있는 1차원 구간으로 변환된다. 이제 여기에서 Maximum overlapping intervals 를 가중치를 고려해서 구하면 된다. 시간복잡도는 O(mlogm)

코드

"""Solution code for "BOJ 19584. 난개발".

- Problem link: https://www.acmicpc.net/problem/19584
- Solution link: http://www.teferi.net/ps/problems/boj/19584

Tags: [sweeping]
"""

import sys

ADD = 1
REMOVE = 2


def main():
    N, M = [int(x) for x in sys.stdin.readline().split()]
    y_coords = []
    for _ in range(N):
        # pylint: disable=unused-variable
        x, y = [int(x) for x in sys.stdin.readline().split()]
        y_coords.append(y)
    events = []
    for _ in range(M):
        u, v, c = [int(x) for x in sys.stdin.readline().split()]
        y1, y2 = y_coords[u - 1], y_coords[v - 1]
        events.append((min(y1, y2), ADD, c))
        events.append((max(y1, y2), REMOVE, -c))

    answer = 0
    traffic = 0
    for _, _, traffic_delta in sorted(events):
        traffic += traffic_delta
        answer = max(answer, traffic)

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
Z O V J L
 
ps/problems/boj/19584.txt · 마지막으로 수정됨: 2023/08/22 14:49 저자 teferi