2018年计蒜之道复赛A题

未分类

---

题意：
有$n$个一次函数,分别用$f_i(x)=a_ix+b_i$表示,给定$x_0$,最大化:

$$\begin{align*} f_{k_n}(f_{k_{n-1}}(...f_{k_1}(x_0))) \end{align*}$$
$\{k_i\}$是$n$的一个全排列.
$1\leq a,b \leq 10^9,1\leq n \leq 10^5$

题解:
显然所有的$f_i=a_ix+b_i$都是单调递增函数.
对$f_i$和$f_j$和同一个自变量$x_0$,有两种可能的答案:

$$\begin{align*} ans_1&=a_i(a_jx_0+b_j)+b_i\\ ans_2&=a_j(a_ix_0+b_i)+b_j \\ ans_1-ans_2&=a_ib_j+b_i-a_jb_i-b_j \end{align*}$$
可知可以确定一个大小关系$H_{ij}$给$f_i$和$f_j$进行排序.
使$f_{k_i}(f_{k_{i+1}}(x_0))\leq f_{k_{i+1}}(f_{k_i}(x_0))$成立$(1\leq i <n).$
下面证明一下排序的正确性：
假设存在相邻的$f_{k_i}$和$f_{k_{i+1}}$是逆序对，即有:
$$\begin{align*} f_{k_i}(f_{k_{i+1}}(x_0))>f_{k_{i+1}}(f_{k_i}(x_0)) \end{align*}$$
显然如果我们调换$k_i$和$k_{i+1}$,结果会变大.
故如果$\{k_i\}$没有按大小关系$H$排好序，则一定存在一种调换使结果变大.