codeforces 1574 C. Slay the Dragon

乔望

2023-12-01

本场比赛其他题目题解

A. Regular Bracket Sequences
B. Combinatorics Homework
C. Slay the Dragon
D. The Strongest Build

C. Slay the Dragon

题目描述

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⋅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⋅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.

Example

input1

output1

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.

题意

你有 $n$ 个英雄，每个英雄都有一个自己的武力值 $a_i$ ，现在有 $m$ 个boss，每次询问给你两个数字 $x, y$ 。

你现在需要从这 $n$ 个英雄中挑一个出来，使其满足：(假设挑选出来的是第 $i$ 个)

$a_i \ge x$
$-a_i + \sum_{j=1}^n a_j \ge y$

当然，可能选不出来一个好的方案，所以你还有魔法，只需要花一块钱就可以将任何一个英雄的武力值加一，并且可以无限使用哦~，但是只生效一回合(>也即每个询问都是独立的)。

问你干掉每个boss需要花多少钱

分析

如果不考虑复杂度的话，我们一个可行的做法是，对于每个询问，我们枚举 $i$ ，计算花费。

其中花费包括两部分 $x-a_i$ ， $y-sum+a_i$ 。

然后我们就可以发现，对于每次独立的询问 $x, y, s u m$ 都是常数，所以我们有，第一部分是单调递减的，第二部分是单调递增的，这说明什么？

说明可以二分啊！

首先，显然需要对这 $n$ 个英雄，按照武力值从小到大排序。

然后二分出一个刚好略小于 $x$ 的 $a_i$ ，然后算 $a_i$ 和 $a_{i+1}$ 的贡献，二者最小值就是答案。

#include <bits/stdc++.h>
using namespace std;

long long f(long long x) {
    if(x > 0) return x;
    else return 0;
}

int main() {
    int n, m;
    long long *a, x, y, sum = 0;
    cin >> n;
    a = new long long[n];
    for(int i = 0; i < n; i++)
        scanf("%lld", &a[i]) , sum += a[i];
    sort(a, a+n);
    cin >> m;
    for(int i = 0; i < m; i++) {
        scanf("%lld%lld",&x, &y);
        int r = lower_bound(a+1, a+n ,x) - a, l = r - 1;
        cout << min(f(x-a[l]) + f(y-sum+a[l]), f(x-a[r]) + f(y-sum+a[r])) << endl;
    }

}