本文共 1614 字，大约阅读时间需要 5 分钟。

题目

题解

题意

定义一种操作：平滑化——$b_n=f(a_n)$
具体操作：

• $b[1]=a[1]$
• $b[n]=a[n]$
• 对于$1<i<n$，$b[i]$为$a[i-1],a[i],a[i+1]$的中位数

定义一个序列$a_n$是稳定指$f(a_n)=a_n$
给出一个01序列$a_n$
求出需要进行多少次平滑化后$a_n$是稳定的，并求出最后稳定的序列是什么

分析

首先思考中位数
因为$a_n$是01序列，那么如果当前位置$i$，$a[i-1]$或者$a[i+1]$=$a[i]$，那么$i$这个位置是不用变的
那么把序列扩大
容易发现只有像0101010……或者1010101……这样的序列才会在平滑化发生改变
那么我们只需要暴力找10交替的序列，记录一下答案

• 当01交替序列的长度为奇数时，需要平滑化的次数是 长度整除2，最后的序列全部都是第一个数
  例如01010，最后就会变成00000
• 当01交替序列的长度为偶数时，需要平滑化的次数是 (长度整除2）-1，最后的序列会是前一半是第一个数，后一半是最后一个数
  例如0101，最后就会变成0011

$O(n)$暴力寻找即可

Code

#include<cstdio>#include<iostream>using namespace std;int n,i,j,k,num,l,ans,a[500005],c[500005];int main(){   	freopen("median.in","r",stdin);	freopen("median.out","w",stdout);	scanf("%d",&n);	for (i=1;i<=n;i++)		scanf("%d",&a[i]);	i=1;	while (i<=n)	{   		num=1;		j=i+1;		while (j<=n)		{   			if ((j-i)%2==0)			{   				if (a[j]!=a[i]) break;				num++;				j++;				}				else			{   				if (a[j]==a[i]) break;				num++;				j++;			}		}		if (num==1) c[i]=a[i];		if (num>1&&num%2==1)		{   			l=num/2;			ans=max(ans,l);			for (k=i;k<j;k++)				c[k]=a[i];			}		if (num>1&&num%2==0)		{   			l=num/2-1;			ans=max(ans,l);			for (k=i;k<=i+num/2-1;k++)				c[k]=a[i];			for (k=i+num/2;k<j;k++)				c[k]=a[j-1];		}		i=j;	}		printf("%d\n",ans);	for (i=1;i<=n;i++)		printf("%d ",c[i]);	fclose(stdin);	fclose(stdout);	return 0;}