https://codeforces.com/contest/1574/problem/C
题目大意
给出 $n \ (2 \le n \le 2 \times 10^5)$ 长的数组 $a$ 其中 $1 \le a_i \le 10^{12}$。
给出 $m \ (\le 2 \times 10^5)$ 个询问，每组询问给出 $x \ (1 \le x \le 10^{12}), y \ (1 \le y \le 10^{18})$，问至少需要多少次给某数 $+1$ 的操作才能使，数组选出某个 $a_i \ge x$ 而且 $sum - a_i \ge y$。
简要题解
考虑如果选出一个 $\ge x$ 的 $a_i$ 则我们只需要补 $y - (sum - a_i)$ 的部分，则我们总会贪心的选最小的 $a_i$。 如果选了一个比 $x$ 小的 $a_i$，则此时需要补的部分是 $x - a_i + y - (sum - a_i)$，此时 $a_i$ 具体的选取对结果没有影响。(实际上由于真正的式子是 $x - a_i + max(0, y - (sum - a_i))$，所以真实情况是，当 $a_i$ 选的较小时，第二部分会多出来，因此实际的 cost 图形如下，所以还是直接选尽量大的比较好，拐点是 $a_i = sum - y$)
^ cost
|
| \
| \
| \---------
|
------------------> a_i
复杂度
$T$：$O((n + q) \log n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
int n; cin >> n;
vector<LL> a(n);
for (LL& i : a) cin >> i;
sort(a.begin(), a.end());
LL sum = 0;
for (LL i : a) sum += i;
int m; cin >> m;
LL x, y;
for (int i = 0; i < m; i++) {
cin >> x >> y;
auto p = lower_bound(a.begin(), a.end(), x) - a.begin();
LL ans = x + y;
if (p) {
LL diff = max(0LL, y - (sum - a[p - 1]));
cmin(ans, diff + (x - a[p - 1]));
}
if (p != n) {
LL diff = max(0LL, y - (sum - a[p]));
cmin(ans, diff);
}
cout << ans << '\n';
}
}
int main() {
int t = 1;
// cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] C. Boxes Packing - Educational Codeforces Round 34 (Rated for Div. 2)