BZOJ 1112: [POI2008]砖块Klo

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

Sample Output

2

HINT

原题还要求输出结束状态时,每柱砖的高度.本题略去.

Source

[Submit][Status][Discuss]

分析

对于一段区间，可以知道将高度改为中位数是最优的，因此我们需要做的是维护一个区间的中位数，以及小于中位数的数字之和和大于中位数的数字之和，这个可以平衡树，可以树状数组+二分查找，或者是线段树上二分，甚至是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