테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.

====== 모바일 광고 입찰 ======

===== 풀이 =====
  * 각 광고지면마다 낙찰받기 위해서 올려야 하는 최소 금액을 계산한다 (= max(0, B_i-A_i)). 계산한 값들중 k번째로 큰 값만큼 입찰가를 올린다면, k개의 지면을 낙찰받을수 있다.
  * k번째로 큰 값을 구하는 것은 정렬한뒤 k번째 원소를 찾으면 된다. 시간복잡도는 O(nlogn)

===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 31246. 모바일 광고 입찰".

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

import sys


def main():
    N, K = [int(x) for x in sys.stdin.readline().split()]
    diffs = []
    for _ in range(N):
        A, B = [int(x) for x in sys.stdin.readline().split()]
        diffs.append(B - A)

    answer = max(0, sorted(diffs)[K - 1])
    print(answer)


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_5}}