Visits: 132

今天做了一道题，叫《蒜头君学代数》，本来觉得是数论知识，没想到是二分答案，这题我想了很久，也是看了题解以后才知道这个思路的。

题目链接：https://www.jisuanke.com/course/615/28897

题目：

蒜头君最近在研究二阶矩阵的行列式的计算：
[ $$\displaystyle det\left(\begin{matrix}a & b \\ c & d \end{matrix}\right)=ad-bc​$$ ]

定义 1：一个 奇异矩阵 是指矩阵的行列式的值为 $0​$。

定义 2：矩阵 $A$ 的 范数 定义为：[ $|A|=\max\sum_{i=1}^{m}\left|a_{i,j}\right|$ ]，即矩阵中所有元素的绝对值的最大值。

现在给定一个 $2\times2$ 的矩阵 $A$，找到一个奇异矩阵 $B$ 满足 [ $|A-B|$ ] 的范数最小。求出 [ $|A-B|$ ]的最小范数。

输入格式：

第一行输入两个整数 [ $a,b(|a|,|b|\leq 10^9)$]，表示矩阵 $A$ 中的第一行元素。

第二行输入两个整数 [$c,d(|c|,|d| \leq 10^9)$]，表示矩阵 $A$ 中的第二行元素。

输出格式：

输出一行浮点数，表示最小的 [ $|A-B|$ ] 的范数。只要结果和标准答案误差在 $10^{-6}$ 以内都被认为是正确的。

样例输入1：

  1 2
  4 3

样例输出1：

  0.500000000

样例输入2：

  1 1
  1 0

样例输出2：

  0.333333333

这是一题二分的题。

首先说明思路，二分的东西就是答案，即所求的最小的范数。

矩阵 $A$ 已知，最小的范数就是二分的值，那么就可以求出矩阵 $B$ 的值的范围。

具体来说，如果$A-B$的范数最小是$x$，那么对于矩阵$A$中的某一个元素$a$，$|a-b|$应该在 $\pm x$ 之间，其中$b$是矩阵$B$中对应位置上的元素值。

这样，就可以求出矩阵$B$的四个位置上的元素的取值范围，各自都是一个长度为$2x$的闭区间，且，至少需要有一个位置上的元素取到端点值，其他位置上的值可以是范围内的任意值。

题目并没有规定必须是整数，所以，范围内的任意实数都是可以取的，也就是说，矩阵$B$的元素的取值是连续的。

下面计算矩阵$B$的行列式的值的可能取值，由于元素的取值是连续的，所以矩阵$B$的行列式的值有无穷多个，不可能一一枚举，然后找是不是有值为$0$的（即奇异矩阵）。

但是也正是因为连续的，所以我们只需要找行列式的值的最大值和最小值，如果矩阵$B$的行列式的值的最大值和最小值跨越了$0$，即，最小值小于等于$0$，最大值大于等于$0$，那么，根据函数的连续性（零点存在定理），一定存在行列式的值为$0$的情况，也就是说，一定存在一种构造，在满足各个元素的取值在给定范围内的情况下，使得矩阵$B$的行列式的值为$0$。

例如，对于样例2，最小值是$\frac{4}{9}$，最大值是 $\frac{16}{9}$，跨越了零点，那么就存在一种构造，在确保至少一个元素取得端点值，其他元素在给定范围内的情况下，使得矩阵$B$为奇异矩阵，例如：[ $$\displaystyle \left(\begin{matrix}\frac{4}{3} & \frac{2}{3} \\ \frac{2}{3} & \frac{1}{3} \end{matrix}\right)$$ ]。

由于这是一个$2\times2​$的矩阵，每个元素的取值范围是一个长度为$2x​$的闭区间，所以，只需要计算 16 种情况，就可以求出矩阵$B​$的行列式的值的取值范围。

下面考虑二分的收缩方向。

显然，初始条件，左端点一定是$0$，因为绝对值。

右端点一定是矩阵$A$中最大的值，因为如果存在一个最小范数比$A$中最大的值还大，记为$m$，那么令矩阵$B$为零矩阵（显然也是一个奇异矩阵），就得到范数为$A$中最大值，找到了一个比$m$更小的范数，矛盾。

简单起见，令右端点为一个无穷大的值也是可以的，反正会收缩回来的。

然后考虑什么时候是left=mid，什么时候是right=mid。

显然，如果存在某个范数满足条件，他未必是最小的，但是，如果给定范数是可行的，那么比他更大的范数也一定是可行的（会令最小值更小，最大值更大，既然原来的最小值和最大值跨越了零点，那么显然现在的范围也是跨越零点的）。

例如，给定一个矩阵$B$，第一行第一列的元素是$10000$，其余元素都是$0$，显然$B$是一个奇异矩阵，那么$A-B$的范数就是$|a_{1,1}-10000|$，这是找到了一个答案，可以令ans=mid，但是这是不是最小的答案呢？不知道，因此，尝试缩小mid，即令right=mid再次尝试。

由此，可以得到核心代码。

while (left < right) {
    double mid = (left + right) / 2;
    if (check(mid)) {
        right = mid;
        ans = mid;
    } else {
        left = mid;
    }
}

代码中，考虑到浮点数的精度问题，left < right应该换成比较差值是不是小于$\epsilon$。

check(double)是一个函数，判断在给定的值作为范数的情况下，能不能构造出一个奇异矩阵$B$，如果能，返回true，那么二分代码中就缩小右端点，否则，说明不能构造出奇异矩阵，那么右移左端点，尝试更大的范数。

函数中，首先计算出$B$每个元素的两个端点值，分别是$A[i]\pm mid$，然后计算 16 种情况下的 $ad-bc$ 找到最大值和最小值，判断是不是跨越零点，即是不是异号。

完整代码如下：

import java.util.Scanner;

public class Main {

    static int[] A = new int[4];

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        for (int i = 0; i < A.length; i++)
            A[i] = in.nextInt();
        double left  =0;
        double right = Integer.MAX_VALUE;
        double ans = right;
        double EPS = 1E-6;
        while (left - right < 0 && left - right < -EPS) {
            double mid = (left + right) / 2;
            if (check(mid)) {
                right = mid;
                ans = mid;
            } else {
                left = mid;
            }
        }
        System.out.println(ans);
    }

    private static boolean check(double mid) {
        double[][] B = new double[4][2];
        for (int i = 0; i < A.length; i++) {
            B[i][0] = A[i] + mid;
            B[i][1] = A[i] - mid;
        }
        double max = Integer.MIN_VALUE;
        double min = Integer.MAX_VALUE;
        for (int i = 0; i < 16; i++) {
            int a = i / 8;
            int b = i % 8 / 4;
            int c = i % 4 / 2;
            int d = i % 2;
            double det = B[0][a] * B[3][d] - B[1][b] * B[2][c];
            max = Math.max(max, det);
            min = Math.min(min, det);
        }
        return max * min <= 0;
    }

}