[bzoj 1112] [POI2008]砖块Klo

n 个数 { hi }, 每次可以选一个 +1 或 -1. 希望存在连续 k 个大小相等的数, 求最少操作次数. (1 ≤ k ≤ n ≤ 10^5, 0 ≤ hi ≤ 10^6) 令 h[i],h[i+1],...,h[i+k-1] 大小相等, 则它们会变成这些数的中位数. 不妨令位置为第二关键字, 使所有数两两不同. 从左到右扫一遍, 维护长度为 k 的区间的中位数, 小于中位数的数之和, 所有数之和. 由于从小到大排序后, 加入或删除一个数, 中位数的位置至多变化 1, 所以我们可以用 set 维护. 类似 [APIO 2015] Palembang Bridges.

typedef pair<int, int> ii;
typedef long long ll;

const int N = 1e5;

int h[N];
set<ii> S;

int main()
{
	int n, k;
	ll s = 0, t = 0;
	scanf("%d%d", &n, &k);
	rep (i, 0, n) scanf("%d", h+i);
	rep (i, 0, k) S.insert(ii(h[i], i)), s += h[i];

	set<ii>::iterator it = S.begin();
	rep (i, 0, k/2) t += it++ -> first;

	ii x = *it;
	ll ans = s - 2*t - (k & 1 ? x.first : 0);
	
	rep (i, k, n)
	{
		int cnt = 0;
		s += h[i] - h[i-k];

		ii y(h[i], i);
		if (y < x) t += h[i], ++cnt;
		S.insert(y);

		y = ii(h[i-k], i-k);
		if (y < x) t -= h[i-k], --cnt;
		else if (y == x) ++it;
		S.erase(y);
		
		if (cnt < 0) t += it++ -> first;
		else if (cnt > 0) t -= (--it) -> first;
		x = *it;
		
		ans = min(ans, s - 2*t - (k & 1 ? x.first : 0));
	}
	printf("%lld\n", ans);
}