\[\begin{eqnarray*}

&&\sum_{i=0}^{n-1}\left(ki+b-a_i\right)^2\\

&=&\sum_{i=0}^{n-1}\left(k^2i^2+b^2+a_i^2+2kbi-2kia_i-2ba_i\right)\\

&=&k^2\sum_{i=0}^{n-1}i^2+nb^2+\sum_{i=0}^{n-1}a_i^2+2kb\sum_{i=0}^{n-1}i-2k\sum_{i=0}^{n-1}ia_i-2b\sum_{i=0}^{n-1}a_i\\

\end{eqnarray*}\]

　　设

\[\begin{eqnarray*}

A&=&\sum_{i=0}^{n-1}i^2\\

B&=&\sum_{i=0}^{n-1}i\\

C&=&\sum_{i=0}^{n-1}ia_i\\

D&=&\sum_{i=0}^{n-1}a_i\\

\end{eqnarray*}\]

　　则只需最小化

\[\begin{eqnarray*}

&&Ak^2+nb^2+2kBb-2kC-2Db\\

&=&nb^2+(2kB-2D)b+Ak^2-2kC\\

\end{eqnarray*}\]

　　这是个关于$b$的二次函数，显然当$b$取$\frac{D-kB}{n}$时取得最小值，将$b$用$k$表示，则

\[\begin{eqnarray*}

&&Ak^2+nb^2+2kBb-2kC-2Db\\

&=&Ak^2+\frac{\left(D-kB\right)^2}{n}+\frac{2kB\left(D-kB\right)}{n}-2kC-\frac{2D\left(D-kB\right)}{n}\\

&=&Ak^2+\frac{-D^2-B^2k^2+2BDk}{n}-2Ck\\

&=&\frac{nAk^2-2nCk-D^2-B^2k^2+2BDk}{n}\\

&=&\frac{\left(nA-B^2\right)k^2+\left(2BD-2nC\right)k-D^2}{n}\\

\end{eqnarray*}\]

　　这也是个关于$k$的二次函数，显然当$k$取$\frac{nC-BD}{nA-B^2}$时取得最小值。直接计算即可，时间复杂度$O(n)$。

 

#include
     
      int n,i,j;double A,B,C,D,k,b;inline void read(int&a){  char c;bool f=0;a=0;  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));  if(c!='-')a=c-'0';else f=1;  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';  if(f)a=-a;}int main(){  for(read(n);i