[Gym100490A] Approximation

题目

分析

这是保序回归问题的特例。

我们直接考虑原题的拓展情况，即求出单调不降的序列 ({b_n}) 使得下式最小：

[sum_{i=1}^nw_i(a_i-b_i)^2 ]

考虑如下性质：

1.如果我们对序列 (a_1,a_2,a_3,...,a_n) 求出使得 (sum_{i=1}^n (a_i-k)^2) 最小的 (k) ，那么一定有 (k=frac{sum_{i=1}^nw_ia_i}{sum_{i=1}^n w_i}) 。

证明：设 (f(k)=sum_{i=1}^nw_i(a_i-k)^2) ，显然它是存在最小值的函数。求导得到 (f'(k)=-2(sum_{i=1}^nw_i)k+2sum_{i=1}^nw_ia_i) ，解出零点为 (k=frac{sum_{i=1}^n w_ia_i}{sum_{i=1}^nw_i}) 。

2.如果 (a_i>a_{i+1}) ，则必然有 (b_i=b_{i+1}) 。

证明：易证。这里不再赘述。

然后我们发现，假设原先 (b_n=a_n) ，那么我们就应该通过调整 (b_i>b_{i+1}) 这种 " 对 " 的方式来满足题目的性质。即，如果存在 (b_i > b_{i+1}) ，我们就应该平衡这两个元素为它们的带权平均数。

如何发现这样的逆序对？考虑从前往后扫描整个序列。假设当前位置为 (i) ，之前得出的 (b) 为 (b_1,b_2,...,b_{i-1}) 。

此时 (b) 必然是单调不降的。如果我们直接加入 (a_i) ，那么我们就需要检查这是否会打破 (b) 的单调性。如果打破了，我们就需要将它和前面的 (b) 元素合并，并计算出新的 (b) 值。可以发现这个过程可以用一个单调栈维护，因而可以做到 (O(n)) 的时间。

然后你还可以发现，本质上求 (b) 就是对 (a) 的前缀和序列 (s) 构成的点集 ((i,s_i)) 求了发下凸包。(b_i) 就是经过 (x=i) 的线段的斜率。

代码

#include <cstdio>
 
typedef long long LL;
 
const int MAXN = 2e5 + 5;
 
template<typename _T>
inline void read( _T &x )
{
	x = 0;char s = getchar();int f = 1;
	while( s > '9' || s < '0' ){if( s == '-' ) f = -1; s = getchar();}
	while( s >= '0' && s <= '9' ){x = ( x << 3 ) + ( x << 1 ) + ( s - '0' ), s = getchar();}
	x *= f;
}
 
template<typename _T>
inline void write( _T x )
{
	if( x < 0 ){ putchar( '-' ); x = ( ~ x ) + 1; }
	if( 9 < x ){ write( x / 10 ); }
	putchar( x % 10 + '0' );
}
 
LL s[MAXN];
int stk[MAXN], l[MAXN], r[MAXN];
int N;
 
double getV( const int id )
{
	return 1.0 * ( s[r[id]] - s[l[id]] ) / ( r[id] - l[id] );
}
 
int main()
{
	freopen( "approximation.in", "r", stdin );
	freopen( "approximation.out", "w", stdout );
	read( N );
	for( int i = 1, a ; i <= N ; i ++ )
		read( a ), s[i] = s[i - 1] + a;
	int top = 0;
	for( int i = 1 ; i <= N ; i ++ )
	{
		r[i] = i, l[i] = i - 1;
		while( top && getV( stk[top] ) >= getV( i ) )
			l[i] = l[stk[top]], top --;
		stk[++ top] = i;
	}
	for( int k = 1 ; k <= top ; k ++ )
		for( int i = l[stk[k]] + 1 ; i <= r[stk[k]] ; i ++ )
			printf( "%.9lf ", getV( stk[k] ) );
	puts( "" );
	return 0;
}