【NOIP2015模拟10.30晚】中位数

思路

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

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

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

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

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