D. PriceFixed #727 Div.2

https://codeforces.com/contest/1539/problem/D
시간 1초, 메모리 256MB

input :

• n (1≤n≤100000)
• ai bi (1 ≤ ai ≤ 10^14, 1 ≤ bi ≤ 10^14)

output :

• Output the minimum sum that Lena needs to make all purchases.
• Lena가 구매할 가장 최소한의 값을 출력 하시오.

조건 :

• The store has an infinite number of items of every product.

• 상점에는 모든 물건들이 무한대로 존재합니다.

• All products have the same price: 2 rubles per item.

• 각각의 상품들은 2루블입니다.

• For every product i there is a discount for experienced buyers: if you buy bi items of products (of any type, not necessarily type i), then for all future purchases of the i-th product there is a 50% discount (so you can buy an item of the i-th product for 1 ruble!).

• 상품 i에 대해서 구매자들에게 할인이 존재합니다. 어떤 상품이든 bi개 만큼 구매 하신다면 그 이후에 i번 상품을 구매하실때에 50% 할인을 받을 수 있습니다(가격이 1루블로 변동)

---

그렇다면 bi가 클수록 이에 해당하기가 힘들다 그렇다면 bi가 작은 놈들에 대해서는 2루블을 사용하고 개수가 충족되었을 때 bi가 작은 놈들을 사면서 움직이면 되겠다.

우선적으로 ai의 값도 변동이 발생 할 것이다. 이를 통해 얼마나 더 물건을 사야할 지 알 수 있기 때문에 tuple이 아닌 2차원 리스트로 만들도록 하자.

그렇다면 bi의 값을 기준으로 오름차순으로 정렬을 한 이후에 인제 수행 할 때에 몇 개를 사는지가 중요한데 이 때에 2가지 경우가 존재한다.

1. 현재까지 구매한 물품(cnt)가 bi보다 크거나 같다.
2. 작다.

1의 경우 ai 만큼 물품을 구매해버리면 된다. 그리고 포인터를 한 칸 오른쪽으로 옮겨준다.
2의 경우에는 bi를 채우기 위해서 bi - cnt만큼 물품을 사도록 한다. 이 물품은 가장 뒤의 물건(right가 가리키는)을 사서 채운다. 그럼 right가 가리키는 물건 사야 하는 횟수가 0이 된다면 right -= 1을 해서 왼쪽으로 옮겨 준다.

그렇게 수행을 해서 right가 left보다 작아질 때 까지 수행한다. 동일한 위치에서도 수행을 계속 해야 한다. 여전히 물건을 사야하기 때문이다.

import sys

n = int(sys.stdin.readline())
data = []
for i in range(n):
    temp = list(map(int, sys.stdin.readline().split()))
    data.append(temp)

data.sort(key=lambda x: x[1])
cnt, ans = 0, 0
left, right = 0, len(data) - 1

while left <= right:
    if data[left][1] <= cnt:
        ans += data[left][0]
        cnt += data[left][0]

        # left에서도 아래에서의 right -= 1에 걸릴 수 있기 때문에 작성이 필요.
        data[left][0] = 0
        left += 1
    else:
        # 아직 bi 기준을 못 채웠기 때문에 음수가 발생할 가능성 없음
        buy = min(data[right][0], data[left][1] - cnt)
        data[right][0] -= buy
        cnt += buy
        ans += buy * 2

        if data[right][0] == 0:
            right -= 1
print(ans)