[백준]🥈 31246 : 모바일 광고 입찰

문제

MOLOCO가 모든 입찰가를 일괄적으로 X만큼 올렸을 때, 최소 K개 이상의 지면을 낙찰받는 음이 아닌 최소 정수 X를 찾는 문제입니다.

주어진 각 광고 지면에 대해 MOLOCO의 입찰가 A와 다른 회사의 최고 입찰가 B가 제공됩니다. MOLOCO가 입찰가를 X만큼 올렸을 때, MOLOCO의 새로운 입찰가는 A + X가 되며, 이 값이 B 이상이면 해당 지면을 낙찰받을 수 있습니다.

이를 수식으로 나타내면 다음과 같습니다:

• A + X ≥ B
• X ≥ B - A

따라서, 각 지면에 대해 B - A 값을 계산하고, 이 값이 X의 최소값이 됩니다. 이러한 값들을 모두 모아 오름차순으로 정렬한 후, K번째로 작은 값을 찾으면 MOLOCO가 최소 K개의 지면을 낙찰받기 위한 최소 X 값을 구할 수 있습니다. 만약 그 값이 음수라면, X는 0이 됩니다.

 

코드

import sys
input = sys.stdin.readline

a,b = map(int, input().split())
x = []

for _ in range(a):
    A,B = map(int, input().split())
    x.append(B-A)
x.sort()

if x[b-1] < 0:
    print(0)
else :
    print(x[b-1])