【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;
}

本文地址：https://blog.csdn.net/auroralbeauty/article/details/107610836