[BZOJ1112] [POI2008]砖块Klo

发布于 2018-09-17  467 次阅读


题目:N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.
第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000


通过读题,发现他大概让你使连续一段序列值相等,每次可以消耗1的代价给某个位置+1或-1.最小化代价。
转化成小学知识,如果给定一维坐标系上的k个点,找一个点,使得它到其它点的距离和最小。
显然这个点是中位数。
所以设中位数为md
$p=\frac{k+1}{2}$
$ans=\min((p-1)\times md -\sum_{(a_i<=md )}a_i-(k-p) \times md +\sum_{a_j>md}a_j)$

然后用平衡树维护区间中位数,大于中位数的数的和,小于等于中位数的数的和。

#include <cstdio>
#include <algorithm>
#include <cstring>

#define int long long 
using namespace std;
const int N=3e5+10;
const int INF=0x3f3f3f3f3f3f3f3f;

struct data
{
    int ch[2];
    int val,prio;
    int siz,cnt;
    int sum;
};

data t[N];
int pool_cur;
int root;
int n,K,h[N];
int ans=INF,sum1,sum2,sum3,mid,tmd;

inline void init()
{
    pool_cur=1;root=0;
}
inline int newnood(int val)
{
    t[++pool_cur].val=val;t[pool_cur].sum=val;
    t[pool_cur].ch[0]=t[pool_cur].ch[1]=0;
    t[pool_cur].prio=rand();
    t[pool_cur].cnt=t[pool_cur].siz=1;
    return pool_cur;
}

inline void pushup(int p)
{
    t[p].siz=t[t[p].ch[0]].siz+t[t[p].ch[1]].siz+t[p].cnt;
    t[p].sum=t[t[p].ch[0]].sum+t[t[p].ch[1]].sum+t[p].val*t[p].cnt;
}
inline void rotate(int &p,int d)
{
    int u=t[p].ch[d];
    t[p].ch[d]=t[u].ch[d^1];
    t[u].ch[d^1]=p; 
    pushup(p);pushup(p=u);
}
inline void insert(int &p,int val)
{
    if(!p){p=newnood(val);return;}
    t[p].sum+=val;
    if(t[p].val==val){t[p].cnt++;t[p].siz++;pushup(p);return;}
    int d=t[p].val<val;
    insert(t[p].ch[d],val);++t[p].siz;
    if(t[t[p].ch[d]].prio<t[p].prio) rotate(p,d);
}
void remove(int &p,int val)
{
    if(!p) return;
    if(t[p].val==val)
    {
        if(t[p].cnt>1){t[p].siz--;t[p].cnt--;t[p].sum-=val;return;}
        if(!t[p].ch[0]){p=t[p].ch[1];return;}
        else if(!t[p].ch[1]){p=t[p].ch[0];return;}
        else 
        {
            int d=t[t[p].ch[0]].prio < t[t[p].ch[1]].prio;
            rotate(p,d^1);
            remove(t[p].ch[d],val);
        }
    }else 
    {
        int d=t[p].val<val;t[p].sum-=val;
        remove(t[p].ch[d],val);
    }
    pushup(p);
}
inline void fk(int p,int k)
{
    while(p)
    {
        if(k<=t[t[p].ch[0]].siz)
        {
            sum2+=(t[p].val*t[p].cnt+t[t[p].ch[1]].sum);
            p=t[p].ch[0];
        //  printf("1:%dn",sum2);
        } 
        else if(k>t[t[p].ch[0]].siz+t[p].cnt)
        {
            sum1+=t[p].val*t[p].cnt+t[t[p].ch[0]].sum;
            k=k-t[t[p].ch[0]].siz-t[p].cnt,p=t[p].ch[1];
        //  printf("2:%dn",sum1);
        }
        else
        {
            sum1+=(t[t[p].ch[0]].sum+(k-t[t[p].ch[0]].siz-1)*t[p].val);
            sum2+=(t[t[p].ch[1]].sum+(t[t[p].ch[0]].siz+t[p].cnt-k)*t[p].val);
            tmd=t[p].val;
        //  printf("3:%d %dn",sum1,sum2);
            return ;
        }
    }
    return ;
}
inline void solve()
{
    sum1=sum2=0;
    fk(root,mid);//printf("tmd=%d sum1=%d sum2=%dn",tmd,sum1,sum2);
    sum3=(mid-1)*tmd-sum1+sum2-(K-mid)*tmd;
    if(sum3<ans) ans=sum3;
}
signed main()
{
    //freopen("wtf.in","r",stdin);
//  freopen("qqq.out","w",stdout);
    init();
    scanf("%lld%lld",&n,&K);
    for(int i=1;i<=n;++i) scanf("%lld",&h[i]);
    mid=((K+1)>>1);
    for(int i=1;i<=K;i++) insert(root,h[i]);
    solve();
    for(int i=K+1;i<=n;i++)
    {
        remove(root,h[i-K]);
        insert(root,h[i]);
        solve();
    }
    printf("%lld",ans);
}

0.00 avg. rating (0% score) - 0 votes

一沙一世界,一花一天堂。君掌盛无边,刹那成永恒。