【NOIP2015模拟10.30晚】中位数_.net

【NOIP2015模拟10.30晚】中位数

思路

分析可得，存在4种情况。

第一种情况，如 $…001100…$ 这种两个相同的数字组成的序列，我们不用进行任何操作。

第二种情况，因为 $a[1]$ 和 $a[n]$ 不变，我们只需要在 $a[0]$ 和 $a[n+1]$ 处分别复制 $a[1]$ 和 $a[n]$ 的值即可。

第三种情况， $…0010101000…$ 这种中间是 $101$ 或 $010$ 交替出现 $1,0$ 的序列，交替序列两边是相同数字的情况，统计 $a[i]!=a[i+1]$ && $a[i]!=a[i-1]$ 的连续的 $i$ 的次数为 $num$ ，则 $ans+=(num+1)/2$ ，新序列中原交替序列部分和两边的数字相同，如该例子得到的结果是 $…0000000000…$ 。

第四种情况， $…00010101111…$ 这种中间是 $101$ 或 $010$ 交替出现的序列，交替序列两边是不同数字的情况，统计 $a[i]!=a[i+1]$ && $a[i]!=a[i-1]$ 的连续的 $i$ 的次数为 $num$ ，则 $ans+=num/2$ ，因为 $num$ 恒为偶数，为了方便，下面的代码写的是 $ans+=(num+1)/2$ ，新序列中原交替部分前一半和交替序列左边的数字相同，后一半和交替序列右边的数字相同，如该例子得到的结果是 $…00000111111…$ 。

code

#include<bits/stdc++.h>
#define ll long long
#define R register
#define mod 1000000007
using namespace std;
inline ll read(){
	ll f=0,pa=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')pa=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){f=(f<<3)+(f<<1)+(ch^48);ch=getchar();}
	return f*pa;
}
inline void write(ll x){
	if(x<0)x=-x,putchar('-');
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
inline void writelp(ll x){write(x);putchar(' ');}
inline void writeln(ll x){write(x);putchar('\n');}
ll n,a[500005],ans,b[500005],s,e,scnt,ecnt,num;
int main(){
	freopen("median.in","r",stdin);
	freopen("median.out","w",stdout);
	n=read();
	for(R ll i=1;i<=n;i++) a[i]=read();
	a[0]=a[1];a[n+1]=a[n];
	for(R ll i=1;i<=n;i++){
		if(a[i]==a[i-1]||a[i]==a[i+1]){
			b[i]=a[i];
			if(scnt){
				e=a[i];ecnt=i-1;
				if(s==e){
					for(R ll j=scnt;j<=ecnt;j++)
					b[j]=s;
				}else{
					for(R ll j=scnt;j<=(scnt+ecnt)/2;j++)
					b[j]=s;
					for(R ll j=(scnt+ecnt)/2+1;j<=ecnt;j++)
					b[j]=e;
				}
				ans=max(ans,(num+1)/2);
				s=0;e=0;scnt=0;ecnt=0;num=0;
			}
		}
		else{
			if(!scnt) s=a[i-1],scnt=i;
			num++;
		}
	}
	writeln(ans);
	for(R ll i=1;i<=n;i++)
	writelp(b[i]);
	return 0;
}