308781: CF1574C. Slay the Dragon
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Slay the Dragon
题意翻译
给定长度为 $n$ 的序列 $a$,$m$ 次询问,每次询问包含两个参数 $x,y$,你可以给序列任意位置 $+1$,最后你需要找出一个位置 $p$ ,满足 - $a_p\ge x$ - $\displaystyle\sum_{i=1}^n a_i[i\not= p] \ge y$ 最小化 $+1$ 次数,输出其次数。 **限制**:$2\le n\le2\times 10^5,1\le m\le 2\times10^5,1\le a_i,x\le 10^{12},1\le y\le 10^{18}$ Translated by 飞丞题目描述
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).输入输出格式
输入格式
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.
输出格式
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.
输入输出样例
输入样例 #1
4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7
输出样例 #1
1
2
4
0
2