[JZOJ4882]多段线性函数

Problem

有\( n\)个变量\(x_1,x_2,\cdots,x_n \in \mathbb{R} \),对于每个变量都有一个限制\(x_i \in [l_i, r_i]\),任意两个变量的取值不想和影响。

给一个多段线性函数

\[ f(y)=\sum_{i=1}^n |y-x_i|\]

定义这个函数的局部最小值\( f_{\text{min}}(y_0)\)为,当\( y\)取某个值\(y_0\)时,存在一种\( x_i\)的取值方案使得函数值为\( f_{\text{min}}(y_0)\),且对于所有的\(x_i\)的取值方案,都有\(f(y_0) \geq f_{\text{min}}(y_0)\)

定义这个函数的全局最小值\( f_{\text{min}} \):存在某个\( y=y_0\),使得\(f_{\text{min}}(y_0)=f_{\text{min}}\),且对于所有的\(y\),都有\( f_{\text{min}}(y)\geq f_{\text{min}}\)。

任务是求出\( y\)的取值范围\( [L, R]\),使得都有\( f_{\text{min}}(y)=f_{\text{min}}\)

可以证明\( [L, R]\)是答案的一般形式,也就是不存在多段的\( y\)满足题意。如果\(y\) 仅能取一个值\(z\),令\(L=R=z\)
继续阅读 [JZOJ4882]多段线性函数

0

[JZOJ4737]金色丝线将瞬间一分为二

Problem

按顺序给出\(N\)个点的坐标\((X_i,Y_i)\),求第一个合法的点,使得当前已经加入的点两两曼哈顿距离之和超过\(K\)。

\(N\in [0,6\times 10^5]\),\(K\in [0,10^{18}]\),\(X_i,Y_i\in [1,10^9]\)
继续阅读 [JZOJ4737]金色丝线将瞬间一分为二

0