Slay the Dragon (Codeforces 1574C)
Tags: Greedy, ternary search

Recently, Petya learned about a new game "Slay the Dragon". As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of $$$n$$$ heroes, the strength of the $$$i$$$-th hero is equal to $$$a_i$$$.According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon's defense is equal to $$$x$$$, then you have to send a hero with a strength of at least $$$x$$$ to kill it. If the dragon's attack power is $$$y$$$, then the total strength of the heroes defending the castle should be at least $$$y$$$.The player can increase the strength of any hero by $$$1$$$ for one gold coin. This operation can be done any number of times.There are $$$m$$$ dragons in the game, the $$$i$$$-th of them has defense equal to $$$x_i$$$ and attack power equal to $$$y_i$$$. Petya was wondering what is the minimum number of coins he needs to spend to defeat the $$$i$$$-th dragon.Note that the task is solved independently for each dragon (improvements are not saved).

Input: The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — number of heroes.The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$), where $$$a_i$$$ is the strength of the $$$i$$$-th hero.The third line contains a single integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of dragons.The next $$$m$$$ lines contain two integers each, $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i \le 10^{12}; 1 \le y_i \le 10^{18}$$$) — defense and attack power of the $$$i$$$-th dragon.

Output: Print $$$m$$$ lines, $$$i$$$-th of which contains a single integer — the minimum number of coins that should be spent to defeat the $$$i$$$-th dragon.

Note: To defeat the first dragon, you can increase the strength of the third hero by $$$1$$$, then the strength of the heroes will be equal to $$$[3, 6, 3, 3]$$$. To kill the dragon, you can choose the first hero.To defeat the second dragon, you can increase the forces of the second and third heroes by $$$1$$$, then the strength of the heroes will be equal to $$$[3, 7, 3, 3]$$$. To kill the dragon, you can choose a second hero.To defeat the third dragon, you can increase the strength of all the heroes by $$$1$$$, then the strength of the heroes will be equal to $$$[4, 7, 3, 4]$$$. To kill the dragon, you can choose a fourth hero.To defeat the fourth dragon, you don't need to improve the heroes and choose a third hero to kill the dragon.To defeat the fifth dragon, you can increase the strength of the second hero by $$$2$$$, then the strength of the heroes will be equal to $$$[3, 8, 2, 3]$$$. To kill the dragon, you can choose a second hero.

Sample Inputs:
4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7

Sample Outputs:
1
2
4
0
2

Solution (Python):
from sys import stdin, stdout
N = int(input())
arr = [int(x) for x in input().split(' ')]
arr.sort()
total = sum(arr)
res = []
from bisect import bisect_left as bl

def solve(r, l, arr, total):
    index = bl(arr, r)
    if index == len(arr):
        return r - arr[-1] + max(l - (total - arr[-1]), 0)
    elif r == arr[index]:
        return max(l - (total - arr[index]), 0)
    elif index == 0:
        return max(l - (total - arr[0]), 0)
    else:
        a = max(l - (total - arr[index]), 0)
        b = r - arr[index - 1] + max(l - (total - arr[index - 1]), 0)
        return min(a, b)
m = int(stdin.readline())
att = []
for i in range(m):
    (l, r) = [int(x) for x in stdin.readline().split(' ')]
    res.append(str(solve(l, r, arr, total)))
stdout.write('\n'.join(res))

Solution (Python):
def bin_search(lst, n):
    lo = 0
    hi = len(lst) - 1
    while lo < hi:
        mid = (lo + hi) // 2
        if lst[mid] >= n:
            hi = mid
        else:
            lo = mid + 1
    if lst[lo] >= n:
        return lo
    else:
        return -1
from bisect import bisect_left
import sys
input = sys.stdin.readline
n = int(input())
a = [*map(int, input().split())]
a.sort()
sz = len(a)
sm = sum(a)
m = int(input())
dragon = []
ans = [None for _ in range(m)]
for i in range(m):
    (x, y) = map(int, input().split())
    bs = bisect_left(a, x)
    if bs != sz:
        coins = 0
        b1 = bs
        b2 = bs - 1
        rem = sm - a[b1]
        coins += max(y - rem, 0)
        coin = 1 << 60
        if b2 >= 0:
            coin = x - a[b2]
            rem = sm - a[b2]
            coin += max(y - rem, 0)
        ans[i] = min(coin, coins)
    else:
        total_req = x - a[sz - 1]
        total_req += max(0, y - (sm - a[sz - 1]))
        ans[i] = total_req
sys.stdout.write('\n'.join(map(str, ans)) + '\n')

Solution (Python):
import sys
input = sys.stdin.readline
from bisect import bisect_left
n = int(input())
a = list(map(int, input().split()))
a.sort()
m = int(input())
s = sum(a)
ans = [None for _ in range(m)]
for q in range(m):
    (x, y) = map(int, input().split())

    def f(v):
        return max(0, x - a[v]) + max(0, y - (s - a[v])) if 0 <= v and v < n else 1 << 60
    p = bisect_left(a, x)
    ans[q] = min(f(p - 1), f(p))
sys.stdout.write('\n'.join(map(str, ans)) + '\n')