1112: [POI2008]砖块Klo
Time Limit: 10 Sec Memory Limit: 162 MB
Submit: 1736 Solved: 606
[Submit][Status][Discuss]
Description
N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.
Input
第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000
Output
最小的动作次数
Sample Input
5 3
3
9
2
3
1
3
9
2
3
1
Sample Output
2
HINT
原题还要求输出结束状态时,每柱砖的高度.本题略去.
Source
分析
对于一段区间，可以知道将高度改为中位数是最优的，因此我们需要做的是维护一个区间的中位数，以及小于中位数的数字之和和大于中位数的数字之和，这个可以平衡树，可以树状数组+二分查找，或者是线段树上二分，甚至是STL set，做法太多……
代码
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #define ri register int #define lim 10000000 char *c = new char[lim]; template <class T>
void read(T &x)
{
x = ; while (*c < '')++c; while (*c >= '')
x = x* + *c++ - '';
} template <class T>
void Min(T &a, T b)
{
if (a > b)a = b;
} template <class T>
void Max(T &a, T b)
{
if (a < b)a = b;
} #define N 1000005 int n, m;
int h[N]; struct node
{
int lt, rt, cnt;
long long sum;
}tree[N * ]; void build(int p, int l, int r)
{
node &t = tree[p]; t.lt = l;
t.rt = r; t.cnt = t.sum = ; if (l ^ r)
{
int mid = (l + r) >> ; build(p << , l, mid);
build(p << | , mid + , r);
}
} void insert(int p, int pos, int val1, int val2)
{
node &t = tree[p]; t.cnt += val1;
t.sum += val2; if (t.lt ^ t.rt)
{
int mid = (t.lt + t.rt) >> ; if (pos <= mid)
insert(p << , pos, val1, val2);
else
insert(p << | , pos, val1, val2);
}
} int query1(int p, int rank)
{
node &t = tree[p]; if (t.lt == t.rt)return t.lt; if (tree[p << ].cnt >= rank)
return query1(p << , rank);
else
return query1(p << | , rank - tree[p << ].cnt);
} long long query2(int p, int l, int r)
{
if (l > r)return 0LL; node &t = tree[p]; if (l == t.lt && r == t.rt)
return t.sum; int mid = (t.lt + t.rt) >> ; if (r <= mid)
return query2(p << , l, r);
if (l > mid)
return query2(p << | , l, r);
return query2(p << , l, mid) + query2(p << | , mid + , r);
} int query3(int p, int l, int r)
{
if (l > r)return 0LL; node &t = tree[p]; if (l == t.lt && r == t.rt)
return t.cnt; int mid = (t.lt + t.rt) >> ; if (r <= mid)
return query3(p << , l, r);
if (l > mid)
return query3(p << | , l, r);
return query3(p << , l, mid) + query3(p << | , mid + , r);
} signed main(void)
{
fread(c, , lim, stdin); read(n);
read(m); ri maxi = ;
ri mini = N; for (ri i = ; i <= n; ++i)
{
read(h[i]); Min(mini, h[i]);
Max(maxi, h[i]);
} build(, , N); for (ri i = ; i < m; ++i)
insert(, h[i], , h[i]); int d = (m + ) >> ; long long ans = 1e18 + ; for (ri i = m; i <= n; ++i)
{
insert(, h[i], , h[i]); {
int mid = d; long long q = query1(, mid), res = 0LL; long long lc = query3(, , q - );
long long rc = query3(, q + , N); res += lc*q - query2(, , q - );
res += query2(, q + , N) - rc*q; Min(ans, res);
} insert(, h[i - m + ], -, -h[i - m + ]);
} printf("%lld\n", ans);
}
BZOJ_1112.cpp
@Author: YouSiki