题目描述

牛牛和 15 个朋友来玩打土豪分田地的游戏，牛牛决定让你来分田地，地主的田地可以看成是一个矩形，每个位置有一个价值。分割田地的方法是横竖各切三刀，分成 16 份，作为领导干部，牛牛总是会选择其中总价值最小的一份田地， 作为牛牛最好的朋友，你希望牛牛取得的田地的价值和尽可能大，你知道这个值最大可以是多少吗？

输入描述:

每个输入包含 1 个测试用例。每个测试用例的第一行包含两个整数 n 和 m（1 <= n, m <= 75），表示田地的大小，接下来的 n 行，每行包含 m 个 0-9 之间的数字，表示每块位置的价值。

输出描述:

输出一行表示牛牛所能取得的最大的价值。

示例1

输入

4 43332323333322323

输出

2

【解决】

① 一样难懂的题意。。。。

1. 要是穷举的话，竖切三刀和横切三刀都得枚举，然后组合在一块是一种方案，随着数据的增大，时间会越来越长O（N^6）。

2. 只枚举竖切的三刀，然后采用二分值寻找横切方案，相当于把横切的穷举O(N^3)变成了O(log(N))，从而在整体上降低了时间复杂度。

3. 二分值方法是利用我们寻找的这个值肯定是在0和所有田地价值总和sum之间，所以使用二分查找，一点点缩小范围。

4. 寻找横切方案时，先假设当前行就是被横切的那一行，那么它新形成的四块地，每块地的价值都得大于等于这个二分值，如果满足条件，就继续寻找下一个横切线，如果最后可以分成比二分值大的16块地（甚至更多，说明二分值偏小），说明该二分值就是我们要找的值（或者此二分值偏小，我们继续调整二分范围）；否则当前分割方案不行，继续枚举下个方案，调整二分范围。

输入示例

4 4 

3332 

3233 

3332 

2323 

输出 

2 

sum矩阵为

3 6 9 11 

6 11 17 22  

9 17 26 33 

11 22 33 43 

mid依次为

21->10->4->1->2

import java.util.Scanner;

/**

 * 网易——分田地,竖切枚举+二分查找,又是一个。。。题  * created by liyurong  **/ public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         while (sc.hasNext()){             int n = sc.nextInt();             int m = sc.nextInt();             int[][] fields = new int[n][m];             for (int i = 0;i < n;i ++){                 char[] tmp = sc.next().toCharArray();                 for (int j = 0;j < m;j ++){                     fields[i][j] = tmp[j] - '0';                 }             }

            int[][] sum = new int[n + 1][m + 1];

            for (int i = 1;i <= n;i ++){                 for (int j = 1;j <= m;j ++){                     sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + fields[i - 1][j - 1];                 }             }

            int left = 0;

            int right = sum[n][m];             int res = 0;             while (left <= right){                 int mid = (right - left) / 2 + left;                 if (judge(mid,n,m,sum)){                     left = mid + 1;                     res = mid;                 }else {                     right = mid - 1;                 }             }             System.out.println(res);         }         sc.close();     }     public static boolean judge(int x,int n,int m,int[][] sum){         for (int i = 1;i <= m - 3;i ++){             for (int j = i + 1;j <= m - 2;j ++){                 for (int k = j + 1;k <= m - 1;k ++){                     int lastRow = 0;                     int count = 0;                     for (int row = 1;row <= n;row ++){                         int sum1 = cal(row,i,lastRow,0,sum);                         int sum2 = cal(row,j,lastRow,i,sum);                         int sum3 = cal(row,k,lastRow,j,sum);                         int sum4 = cal(row,m,lastRow,k,sum);                         if (sum1 >= x && sum2 >= x && sum3 >= x && sum4 >= x){                             lastRow = row;                             count ++;                         }                     }                     if (count >= 4){                         return true;                     }                 }             }         }         return false;     }     public static int cal(int x,int y,int i,int j,int[][] sum){         return sum[x][y] - sum[i][y] - sum[x][j] + sum[i][j];     } }