Atcoder ABC 255 D

我们又双叒叕见面啦！

今天，我就来把ABC255的D题给说一说！

这题给我的第一反应是：妈呀，怎么这么简单！
看到 $ Q \le 2 \times 10 ^ 5 $ 时，我又慌了，这咋办呀！

思路

首先如果只有一组的话，那么直接算 $ \Sigma ^ {n} _ {i=1} |a_i - x| $ 就行了。
但是这有很多组，暴力不行。
考虑绝对值优化：
比 $ x $ 小的算 $ mx - sum $，
比 $ x $ 大的算 $ sum - mx $。
考虑二分 $ x $ ，再排一次序，算前、后缀和，就做完了。
时间复杂度：$ O(n log n) $

代码

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

#define maxn 200005

long long A[maxn];
long long prefix[maxn], suffix[maxn];

int main() {
	int N, Q;
	scanf("%d %d", &N, &Q);
	for (int i = 0; i < N; i++) {
		scanf("%lld", &A[i]);
	}
	sort(A, A + N);
	prefix[0] = A[0];
	for (int i = 1; i < N; i++) {
		prefix[i] = prefix[i - 1] + A[i];
	}
	suffix[N - 1] = A[N - 1];
	for (int i = N - 2; i >= 0; i--) {
		suffix[i] = suffix[i + 1] + A[i];
	}
	while (Q--) {
		long long X;
		scanf("%lld", &X);
		long long int * place = lower_bound(A, A + N, X);
		int idx = place - A;
		printf("%lld\n", ((idx) * X - prefix[idx - 1]) + (suffix[idx] - (N - idx) * X));
	}
	return 0;
}
题解

相关

洛谷P5340 大中锋的游乐场 题解 分层图最短路

Ubuntu 断网问题解决

[SQL] SQL Server 2019 中LocalDB 报错的问题解决

题解 Count on a tree II/【模板】树分块

HttpURLConnection发送中文乱码问题解决

1675: [Usaco2005 Feb]Rigging the Bovine Election 竞选划区（题解第一弹）

P7715 「EZEC-10」Shape 题解

Proguard混淆之后行数LineNumber对不上问题解决

ZYNQ xilinx_axienet CPU软中断占用过高问题解决记录

题解 P6345 [CCO 2017]接雨滴

魔咒词典 - 题解【暴搜】

最大数maxnumber - 题解【树状数组】

标签