[计蒜之道复赛 2018] 贝壳找房函数最值
微扰法证明贪心。
Description
贝壳找房的攻城狮最近在研究一次函数 \(f(x) = ax + b\)。
现在有 \(n\) 个一次函数，\(f_i(x) = a_ix+b_i,\ i = \{1 … n\}\)。
容易发现，一次函数嵌套一次函数，还是一次函数。
\]
给定 \(x\)，并且对于所有的 \(f_i(x)\) 可以任意改变顺序嵌套函数，求 \(f(f(f(…f(x))…)\)的最大值。
Input
一个整数 \(T ( T \le 20 )\) 代表数据组数。
每组数据：
第一行两个整数 \(n,\ x\) 代表一共有 \(n\) 个函数 \(( 1 \le n \le 10000,\ 0 \le x \le 9)\)。
第二行 \(n\) 个整数代表 \(a_{i}\) ,\(1 \le a_{i} \le 9\) 。
第三行 \(n\) 个整数代表 \(b_{i}\), \(1 \le b_{i} \le 9\) 。
Output
为了使问题简化，对于每组数据只需要输出最大值的个位即可。（比如函数的值可能是 \(19\) 或者 $ 23$ ，但最终应该输出的是 \(3\) ）。
Solution
这题按照 \((a-1)/b\) 的大小排序就好。
以下证明：
先解决 \(x\) 的问题。
假设当前有三个函数，参数分别为 \(a_i,a_j,a_p\) 和 \(b_i,b_j,b_p\)。
假设嵌套顺序是 \(f_i(f_j(f_p(x)))\)
那么得到的函数将是
\(ans=a_i(a_j(a_px+b_p)+b_j)+a_j\\\quad\;\;=a_i(a_ja_px+a_jb_p+b_j)+a_j\\\quad\;\;=a_ia_ja_px+a_ia_jb_p+a_ib_j+a_j\)
观察到与 \(x\) 有关的一项跟函数的嵌套顺序无关，所以我们只需要让后面的 \(a_i\times b_j \times …\) 最大即可。
继续假设。考虑一种简单点的情况，即当 \(n=3\) 时，三个方程编号分别是 \(i,j,k\)。
我们通过调整法证明排序策略。
假设最外层嵌套的是第 \(i\) 个方程，那么我们需要决定的就是 \(j,k\) 谁在内层的问题。
先计算出两种情况的答案，分别是 \(p\) 在内层 \(a_ia_jb_p+a_ib_j+b_i\) 和 \(j\) 在内层 \(a_ia_pb_j+a_ib_p+b_i\)。
化简式子，分别是 \(a_jb_p+b_j\) 和 \(a_pb_j+b_p\)。
移项，\((a_j-1)b_p\) 和 \((a_p-1)b_j\)
两边除过去，\((a_j-1)/b_j\) 和 \((a_p-1)/b_p\)
假设 \((a_j-1)/b_j>(a_p-1)/b_p\)，那么最后的答案就是 \(p\) 在内层的答案要大于 \(j\) 在内层的答案。
所以按照 \((a-1)/b\) 排序即可。
证毕。
Code
#include<cstdio>
#include<cctype>
#include<algorithm>
int T;
int n,m,tot;
struct Node{
int a,b;
friend bool operator<(Node x,Node y){
return (x.a-1)*y.b>(y.a-1)*x.b;
}
}node[10005];
int getint(){
int x=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x;
}
signed main(){
T=getint();
while(T--){
tot=1;
n=getint(),m=getint();
for(int i=1;i<=n;i++){
node[i].a=getint();
tot=tot*node[i].a%10;
}
int ans=tot*m%10;
for(int i=1;i<=n;i++)
node[i].b=getint();
std::sort(node+1,node+1+n);
tot=1;
for(int i=1;i<=n;i++){
ans=(ans+tot*node[i].b%10)%10;
tot=tot*node[i].a%10;
}
printf("%d\n",ans%10);
}
return 0;
}