自动搬运

查看原文

来自洛谷，原作者为

	ModestCoder_ 这个家伙不懒，但还是什么也没有留下

搬运于2025-08-24 21:35:44，当前版本为作者最后更新于2019-03-07 21:11:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门

题目大意：

一串长度为n的数，进行一次操作可将其中一个数+1或-1，问最少进行多少次操作，使得数列中有一段长度为k，且大小相同的数

思路：

先考虑如何进行最少次的操作可将一串长度为k的数变成大小相同 显然是将这段数的大小都变成中位数，可是操作数最少 比如1 2 3，若把数都变成3，则需要3-1+3-2=3次操作；若把数变成2（中位数），则需要3-2+2-1=2次操作

所以现在考虑如何找到一串数中的中位数，以及找到中位数后，如何进行统计操作总数 我们一个一个来

找中位数

排序？先进行排序，中位数就找到了，但是时间复杂度太高，淘汰 堆？利用堆维护，开一个大根堆一个小根堆……太麻烦，而且本题需要支持插入和删除操作 数据结构！用树状数组即可求得一段数的中位数，详细请点击这里，不过本题需要再做一个小改动，设当前数组c，那么插入为add(i,1)，删除为add(i - K, -1);

求操作总数

操作可分为两种，+1和-1 即原数列中有两种数，比大于中位数的数与小于中位数的数

大于中位数的数，要把它变成中位数，需要进行(该数-中位数)次操作 小于中位数的数，要把它变成中位数，需要进行(中位数-该数)次操作

我们现在可以知道这段数中的中位数，以及它的位置， 那么操作总数等于（前方高能）：（小于中位数的数的个数 * 中位数 - 小于中位数的数之和）+（大于中位数的数之和 - 大于中位数的数的个数 * 中位数）

这些家伙都可以用树状数组维护 数的个数跟前面求中位数一起维护了（用同一个树状数组） 数的和则需再开一个树状数组，维护前缀和即可

另外，此题要开long long， 要离散化进行操作

Code：

//tree1维护数的个数，tree2维护数的和
#include <bits/stdc++.h>
#define res register int
#define ll long long
#define maxn 500010
using namespace std;

inline ll read(){
	ll s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48);
	return s * w;
}
struct node{
	ll x; 
	int num;
};
node b[maxn];
int tree1[maxn], n, K, p, c[maxn];
ll tree2[maxn], a[maxn], val[maxn];

inline bool cmp(node x, node y){ return x.x < y.x; }
inline int lowbit(int x){ return x & -x; }
inline void add1(int x, int y){ for (; x <= p; x += lowbit(x)) tree1[x] += y; }
inline void add2(int x, ll y){ for (; x <= p; x += lowbit(x)) tree2[x] += y; }
inline int query1(int x){ int sum = 0; for (; x; x -= lowbit(x)) sum += tree1[x]; return sum; }
inline ll query2(int x){ ll sum = 0; for (; x; x -= lowbit(x)) sum += tree2[x]; return sum; }

inline int find(int x){ //二分配合树状数组查找中位数
	int ans = 0, l = 0, r = p;
	while (l <= r){
		int mid = (l + r) >> 1; 
		if (query1(mid) >= x) ans = mid, r = mid - 1; else l = mid + 1;
	}	
	return ans;
}

int main(){
	n = read(), K = read();
	for (res i = 1; i <= n; ++ i) a[i] = read(), b[i].x = a[i], b[i].num = i;
	sort(b + 1, b + 1 + n, cmp);
	b[0].x = b[1].x - 1; 
	for (res i = 1; i <= n; ++ i) c[b[i].num] = b[i].x == b[i - 1].x ? p : ++p, val[p] = b[i].x;//离散化，val数组记录离散后的数对应的原数
	for (res i = 1; i <= K; ++ i) add1(c[i], 1), add2(c[i], a[i]);
	ll ans = 0x3f3f3f3f3f3f3f3f; 
	for (res i = K + 1; i <= n + 1; ++ i){  
		int tmp = find((K + 1) >> 1);
		ll mid = val[tmp];
		ans = min(ans, query1(tmp - 1) * mid - query2(tmp - 1) + query2(p) - query2(tmp) - (query1(p) - query1(tmp)) * mid);
		if (i == n + 1) break; 
		add1(c[i - K], -1); add1(c[i], 1);
		add2(c[i - K], -a[i - K]); add2(c[i], a[i]);
	}
	printf("%lld\n", ans);
	return 0;
}