사용자 도구

사이트 도구


ps:problems:boj:31411

대회 개최

ps
링크acmicpc.net/…
출처BOJ
문제 번호31411
문제명대회 개최
레벨골드 1
분류

투포인터

시간복잡도O(NKlog(NK))
인풋사이즈N<=1000, K<=1000
사용한 언어Python 3.11
제출기록141964KB / 1828ms
최고기록1460ms
해결날짜2024/03/05
출처

제3회 보라매컵 본선 Open Contest - E

풀이

  • 주어진 난이도 커브 공식 $ |x_0-x_1| + |x_1-x_2| + ... + |x_{N-1} - x_{N}| $ 을 바꿔쓰면 max(x) - min(x) 이 된다. 그러므로 문제들의 난이도들이 결정되면, 난이도커브값은 가장 어려운 난이도와 가장 쉬운 난이도의 차이가 된다.
  • 가장 어려운 난이도와 가장 쉬운 난이도의 차이가 최소화 되는 난이도들을 구하면 된다. 모든 문제의 난이도들을 정렬해서 하나의 배열에 저장해두자. 이렇게 하면 모든 문제 종류를 포함하면서 최댓값과 최솟값의 차이가 가장 작은 부분구간을 찾는 문제로 바꿀수 있다. 이것은 투포인터를 이용해서 푸는 전형적인 형태의 문제가 된다. 시간복잡도는 정렬에 O(NKlog(NK)), 투포인터 서치에 O(NK), 총 O(NKlog(NK))가 된다.

코드

"""Solution code for "BOJ 31411. 대회 개최".

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

Tags: [two pointer]
"""

import sys
from teflib import twopointer


def main():
    # pylint: disable=unused-variable
    N, K = [int(x) for x in sys.stdin.readline().split()]
    problems = []
    for i in range(N):
        d_i = [int(x) for x in sys.stdin.readline().split()]
        problems.extend((d_ij, i) for d_ij in d_i)

    difficulties, algos = zip(*sorted(problems))
    answer = min(
        difficulties[end - 1] - difficulties[beg]
        for beg, end in twopointer.minimal_ranges_with_k_unique_elems(algos, N)
    )

    print(answer)


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
X D Q I A
 
ps/problems/boj/31411.txt · 마지막으로 수정됨: 2024/03/05 15:02 저자 teferi