[POI2008]砖块Klo

题目描述

N柱砖,希望有连续K柱的高度是一样的. 你可以选择以下两个动作 1:从某柱砖的顶端拿一块砖出来,丢掉不要了. 2:从仓库中拿出一块砖,放到另一柱.仓库无限大. 现在希望用最小次数的动作完成任务.

输入格式

第一行给出N,K. (1 ≤ k ≤ n ≤ 100000), 下面N行,每行代表这柱砖的高度.0 ≤ hi ≤ 1000000

输出格式

最小的动作次数

分析:

我们已知直接枚举区间然后枚举值是n^2的复杂度,然后我们思考发现我们每次取一段区间的中位数作为到达高度然后算是最优的…那么我们只需要用treap维护区间的中位数就好了….

代码:

#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
#define db double
#define fi first
#define se second
const LL N=1e5+10;
const LL inf=1e18;
const LL mod=12345678;
const double eps=1e-9;
using namespace std;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
namespace Treap
{
    int cnt=0,root;
    struct Node {LL key,sum;int siz,p,ch[2];}node[N];
    Node new_node(LL key)
    {
        node[++cnt].key=key;
        node[cnt].sum=key;
        node[cnt].p=rand();
        node[cnt].siz=1;
    }
    void updata(int now)
    {
        int l=node[now].ch[0],r=node[now].ch[1];
        node[now].siz=node[l].siz+node[r].siz+1;
        node[now].sum=node[l].sum+node[r].sum+node[now].key;
    }
    int merge(int x,int y)
    {
        if(node[x].siz==0) return y;
        if(node[y].siz==0) return x;
        if(node[x].p<node[y].p)
        {
            node[x].ch[1]=merge(node[x].ch[1],y);
            updata(x);return x;
        }
        else
        {
            node[y].ch[0]=merge(x,node[y].ch[0]);
            updata(y);return y;
        }
    }
    void split_k(int now,int &x,int &y,int k)
    {
        if(node[now].siz==0) {x=y=0;return;}
        if(node[node[now].ch[0]].siz+1<=k) x=now,split_k(node[now].ch[1],node[now].ch[1],y,k-node[node[now].ch[0]].siz-1);
        else y=now,split_k(node[now].ch[0],x,node[now].ch[0],k);
        updata(now);
    }
    void split_key(int now,int &x,int &y,LL k)
    {
        if(node[now].siz==0) {x=y=0;return;}
        if(node[now].key<=k) x=now,split_key(node[now].ch[1],node[now].ch[1],y,k);
        else y=now,split_key(node[now].ch[0],x,node[now].ch[0],k);
        updata(now);
    }
    int a,b,c,d,e,f;
}
using namespace Treap;
int n,k;
LL x[N],ans=inf;
signed main()
{
    read(n),read(k);
    for(int i=1,v;i<=n;i++) read(x[i]);
    int now=1;
    for(int i=1;i+k-1<=n;i++)
    {
        while(now<=i+k-1)
        {
            split_key(root,a,b,x[now]);
            new_node(x[now]);
            b=merge(cnt,b);
            root=merge(a,b);
            now++;
        }
        split_k(root,a,b,k/2);
        split_k(b,c,d,1);
        LL mid=node[c].key;
        ans=min(ans,1ll*(1ll*k/2*mid-node[a].sum)+1ll*(node[d].sum-1ll*mid*(k/2-(k%2==0?1:0))));
        b=merge(c,d);
        root=merge(a,b);
        split_key(root,a,b,x[i]-1);
        split_k(b,c,d,1);
        root=merge(a,d);
    }
    printf("%lld\n",ans);
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注