POI 2008 KLO-Building blocks

~{→看不见LaTex格式的Dalao们请刷新本页Thanks♪(･ω･)ﾉ←}~

2019寒假集训题

#.KLO-Building blocks

题面

Byteasar loved to play with building blocks as a child.

He used to arrange the blocks into nnn columns of random height and then organize them in the following manner:

Byteasar would choose a number $k$ and try to arrange the blocks in such a way that some $k$ consecutive columns would be of equal height. Furthermore he always tried to achieve this goal in a minimum number of moves possible, where a single move consists in:

laying one block on top of any column (Byteasar had a huge box with spare blocks, ensuring this move could always be performed), or removing the uppermost block from the top of any column.

However, Byteasar was never quite sure if his sequence of moves was indeed optimal, therefore he has asked you to write a programme that will help him solve the problem.

Task Write a programme that:

reads the number $k$ along with the initial setup of the blocks from the standard input,determines the optimal solution (shortest possible sequence of moves),writes out the solution to the standard output.

---

简要翻译

有$N$柱砖,希望有连续$K$柱的高度是一样的. 你可以选择以下两个动作

$1.$从某柱砖的顶端拿一块砖出来,丢掉不要了.

$2.$从仓库中拿出一块砖,放到另一柱.仓库无限大.

现在希望用最小次数的动作完成任务.你还要求输出结束状态时,每柱砖的高度。

---

Input

第一行输入两个整数$n$和$k$。

以下包含$n$行每行包含一个整数$h_i$代表砖的高度。

---

Output

The optimal solution should be written out to the standard output, ie. such arrangement of blocks that:

contains $k$ consecutive columns of equal height, can be obtained from the initial setup in a minimum possible number of moves.

The output should consist of $n+1$ lines, each one containing a single integer.

The number in the first line should be the minimum number of moves needed to get the desired arrangement.

The line no. $i+1$ (for $1\le i\le n$) should contain the number $h_i$ - the final height of the $i_{th}$ column.

If more than one optimal solution exists, write out one chosen arbitrarily.

---

Sample Input

5 3
3
9
2
3
1

---

Sample Output

2
3
9
2
2
2

---

Hint

$1\le k\le n\le 100,000$

$0\le h_i\le 1,000,000$

---

说明

本题SPJ的提示说明（按照SPJ判断顺序给出）：

Out of Range:输出的数字不在答案可能的范围内。

Wrong Solution:输出方案中不包含连续k个相同高度的柱。

Wrong Result:提交的程序的步数和输出方案的步数不相等。

Expected cost = a,found cost = b:期望步数为a，程序的步数为b。

OK!Correct Answer!:答案正确。

---

题解自行luogu

---

Code

#include<bits/stdc++.h>
using namespace std;
long long read()
{
	long long x=0,w=0;
	char ch=0;
	while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
	while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return w? -x:x;
}
const int N=1e5+10,M=1e6+10;
struct seg_tree
{
	long long l,r,w,s;
}t[M*23];
long long n,k;
long long root[N],cnt,w[N],result=1e16,root_,tot,b,dd;
void pushup(int rot)
{
	t[rot].w=t[t[rot].l].w+t[t[rot].r].w;
	t[rot].s=t[t[rot].l].s+t[t[rot].r].s;
}
void insert(int last,int rot,long long pos,int l=0,int r=1000000)
{
	if(l==r)
	{
		t[rot].w=t[last].w+1;
		t[rot].s=t[last].s+l;
		return;
	}
	int mid=l+r>>1;
	if(pos<=mid)
	{
		t[rot].l=++cnt;
		t[rot].r=t[last].r;
		insert(t[last].l,t[rot].l,pos,l,mid);
	}
	else
	{
		t[rot].r=++cnt;
		t[rot].l=t[last].l;
		insert(t[last].r,t[rot].r,pos,mid+1,r);
	}
	pushup(rot);
}
int k_th(int last,int rot,long long pos,int l=0,int r=1000000)
{
	if(l==r) return l;
	int mid=l+r>>1;
	long long s=t[t[rot].l].w-t[t[last].l].w;
	if(pos<=s) return k_th(t[last].l,t[rot].l,pos,l,mid);
	else return k_th(t[last].r,t[rot].r,pos-s,mid+1,r);
}
long long sum(int last,int rot,long long pos,int l=0,int r=1000000)
{
	if(l==r) return min(pos,t[rot].w-t[last].w)*l;
	int mid=l+r>>1;
	long long s=t[t[rot].l].w-t[t[last].l].w;
	if(pos<=s) return sum(t[last].l,t[rot].l,pos,l,mid);
	else return t[t[rot].l].s-t[t[last].l].s+sum(t[last].r,t[rot].r,pos-s,mid+1,r);
}
int main(int argc, char const *argv[])
{
	n=read(),k=read();
	for(int i=1;i<k;++i)
	{
		tot+=(w[i]=read());
		root[i]=++cnt;
		insert(root[i-1],root[i],w[i]);
	}
	for(int i=k;i<=n;++i)
	{
		w[i]=read();
		root[i]=++cnt;
		tot+=w[i]-w[i-k];
		insert(root[i-1],root[i],w[i]);
		int pos=k+1>>1;
		int id=k_th(root[i-k],root[i],pos);
		long long ans=sum(root[i-k],root[i],pos);
		ans=tot-(ans<<1)-(k-2*pos)*id;
		if(ans<result)
			dd=i,result=ans,b=id;
	}
	printf("%lld\n",result);
	for(int i=1;i<=n;++i)
		if(dd>=i&&dd<i+k) printf("%lld\n",b);
		else printf("%lld\n",w[i]);
	return 0;
}