思路
因为 \(1 \leq n,q \leq 2 \times 10^5\)，所以对于每一次查询的时间复杂度一定要达到 \(\Theta(\log n)\)，甚至于 \(\Theta(1)\)。
一个最简单的想法，我们先统计出整个序列 \(a\) 的和 \(sum\)，然后答案是 \(|sum - x \times n|\)。
很显然，这个想法是错误的，因为对于 \(a\) 中只有两个元素 \(x - 1,x + 1\) 的时候，这样算出来答案为 \(0\)，但是，这种情况答案应该是 \(2\)。
那么，换一个思路。
不难发现，对于一个数 \(a_i\)，它的操作次数满足如下 \(3\) 个结论：
- 当 \(a_i < x\) 时，将操作 \(x - a_i\) 次。
- 当 \(a_i = x\) 时，将操作 \(0\) 次。
- 当 \(a_i > x\) 时，将操作 \(a_i - x\) 次。
那么，我们不妨令序列 \(b\) 中存储了 \(a\) 中小于 \(x\) 的元素，\(c\) 中存储了 \(a\) 中大于 \(x\) 的元素。
很显然，答案就是（\(B,C\) 分别为 \(b,c\) 中的元素个数）：
\[ \sum_{i = 1}^{B}{b_i} + \sum_{i = 1}^{C}{c_i} \]因此，现在的问题就转化为了求 \(b\) 和 \(c\)。
我们发现，对于此题，打乱 \(a\) 的顺序，对答案的正确性无关，于是，我们对 \(a\) 从小到大排一次序。
那么，我们就可以用二分查找出分界点 \(x\) 的位置 \(id\)。所以，在 \(id\) 之前的元素应在 \(b\) 中；反之，应在 \(c\) 中。
其实我们的答只于 \(b,c\) 的和有关，与 \(b,c\) 中真正有哪些元素无关。所以我们并不用求出 \(b,c\)。
因此，我们可以对排序过后的序列 \(a\) 做一个前缀和，然后二分即可。
特别的，对于序列中没有 \(x\) 的情况，答案应为 \(|s_n - x \times n|\)。
时间复杂度 \(\Theta(q \log n)\)
Code
#include <bits/stdc++.h>
#define int long long
#define re register
using namespace std;
const int N = 2e5 + 10;
int n,q;
int arr[N],s[N];
inline int read(){
int r = 0,w = 1;
char c = getchar();
while (c < '0' || c > '9'){
if (c == '-') w = -1;
c = getchar();
}
while (c >= '0' && c <= '9'){
r = (r << 1) + (r << 3) + (c ^ 48);
c = getchar();
}
return r * w;
}
signed main(){
n = read();
q = read();
for (re int i = 1;i <= n;i++) arr[i] = read();
sort(arr + 1,arr + 1 + n);
for (re int i = 1;i <= n;i++) s[i] = s[i - 1] + arr[i];
while (q--){
int x;
x = read();
int id1 = lower_bound(arr + 1,arr + 1 + n,x) - arr - 1;//因为有可能有多个值为 x 的元素，所以求出值为 x 的区间的边界
int id2 = upper_bound(arr + 1,arr + 1 + n,x) - arr;
if (!id1 || id1 == n){//没查到
printf("%lld\n",abs(s[n] - n * x));
continue;
}
int pre = abs(id1 * x - s[id1]);//求答案
int nxt = abs((n - id2 + 1) * x - (s[n] - s[id2 - 1]));
printf("%lld\n",pre + nxt);
}
return 0;
}