大学ACM学习笔记

高斯消元

该来的总会来的系列

int gauss()
{
    for(int i=1;i<=n;i++)//按照列来枚举，当前之前i-1列全消完了 
    {
        int k=i;
        for(int j=i+1;j<=n;j++)if(fabs(a[j][i])>fabs(a[k][i]))k=j;//找一个系数绝对值最大的放在当前行，方便消元 
        if(fabs(del=a[k][i])<eps)return 0;
        for(int j=i;j<=n+1;j++)swap(&a[i][j],&a[k][j]);
        for(int j=i;j<=n+1;j++)a[i][j]/=del;//把第i行的同时除系数 
        for(int j=1;j<=n;j++)
            if(j!=i)
            {
                del=a[j][i];
                for(int k=i;k<=n+1;k++)a[j][k]-=a[i][k]*del;
            }
    }
    return 1;
}

在大学，背诵代码不是那么重要了，重要的还是积累，这个高斯消元就是标准的把一个n*n方阵消成上三角形，然后这个程序比较优秀的是一遍消下面一遍消上面，所以一下子就变成了对角线上全为1的矩阵了，十分方便。

求n个点曼哈顿距离极值

先假设为三维的，就是求 $ max { |a_i-a_j| + |b_i-b_j| + |c_i-c_j| } $
我们有绝对值不等式得$ |a|+|b| \geq |a+b| $
$ |a_i-a_j| + |b_i-b_j| + |c_i-c_j| = \pm a_i \pm a_j \pm b_i \pm b_j \pm c_i \pm c_j $

大学ACM学习笔记

原文：https://www.cnblogs.com/FYH-SSGSS/p/11841402.html