编程题：分田地

秒速五厘米 2022-05-23 01:58 137阅读 0赞

## 题目描述 ##

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

## 输入描述: ##

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

## 输出描述: ##

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

示例1

## 输入 ##

复制

4 4
    3332
    3233
    3332
    2323

## 输出 ##

复制

### 算法思路 ###

分析题目，题目的目的其实就是把田地分为16分，怎样分使16份中最小的一块田地最大。如果单用暴力的方法来求解，要列举所有的分割方法，然后计算其中最小的田地大小，可见复杂度之大。

换个角度思考，通过二分法来求得最小的田地（最大）的情况下的大小，l=0，r=sum\[n\]\[m\],其中sum\[i\]\[j\]表示的是从左上方框到ij方框的田地的大小。接下来开始二分查找，先暴力列举出所有竖切的可能性，然后开始横切，每切一刀前，判断如果每一刀横切所得的四个矩形的大小大于mid，则继续在此基础上横切，否则退出该种可能，调整l和r的空间，不断缩小空间（注意既然mid是最小田地的大小，则就应该满足每一块田地的大小要大于等于mid）。

#### 代码： ####

package net.stxy.one.controller;
    
    /**
     * Created by ASUS on 2018/5/30
     *
     * @Authod Grey Wolf
     */
    import java.util.Arrays;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    
    public class Test2 {
    
    
        public static void main(String[] args) {
            Test2 test2=new Test2();
            test2.sys();
    
        }
    
        private void sys() {
            Scanner scanner=new Scanner(System.in);
            int n,m,i,j;
            while (scanner.hasNext()){
                String[] nm=scanner.nextLine().split(" ");
                //n行
                n=Integer.valueOf(nm[0]);
                //m列
                m=Integer.valueOf(nm[1]);
                int [][]map=new int[n][m];
                for(i=0;i<n;i++){
                    String string=scanner.nextLine();
                    for(j=0;j<m;j++){
                        map[i][j]=string.charAt(j)-'0';
                    }
                }
                /**
                 * sum[i][j]表示满足条件左上角坐标为(0,0),右下角坐标为(i-1,j-1)的矩阵:中所有元素的和值
                 */
                int [][]sum=new int[n+1][m+1];
                for(i=1;i<=n;i++){
                    for(j=1;j<=m;j++){
                        sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i-1][j-1];
                    }
                }
                int low=0,high=sum[n][m];
                int mid;
                int result=0;
                while (low<high){
                    mid=(low+high)/2;
                    if(isValid(n,mid,m,sum)){
                        low=mid+1;
                        result=mid;
                    }else {
                        high=mid-1;
                    }
                }
                System.out.println(result);
            }
        }
    
        /**
         * 是否存在一种切法,使得田地被切割后,最小块矩阵的价值>=mid(这一判定条件为true时:刀的横切数目>=4即可)
         * @param mid
         * @param n
         * @param m
         * @param sum
         * @return
         */
        private boolean isValid(int n, int mid, int m, int[][] sum) {
            int i,j,k,r;
            //记录上一次横切时的行号,因为fields[]是从0行开始的,所以这里从0开始
            int lastRowNum=0;
            //记录横切刀数
            int count=0;
            for (i=1;i<=m-3;i++){
                for(j=i+1;j<=m-2;j++){
                    for (k=j+1;k<=m-1;k++){
                        for (r=1;r<=n;r++){
                            int c1=getMaxValue(r,i,lastRowNum,0,sum);
                            int c2=getMaxValue(r,j,lastRowNum,i,sum);
                            int c3=getMaxValue(r,k,lastRowNum,j,sum);
                            int c4=getMaxValue(r,m,lastRowNum,k,sum);
                            //可以横切一刀的条件
                            if(c1>=mid&&c2>=mid&&c3>=mid&&c4>=mid){
                                lastRowNum=r;
                                count++;
                            }
                        }
                        if(count>=4){
                            return true;
                        }
                    }
                }
            }
            return  false;
        }
    
        /**
         * 设原始土地矩阵为:
         * 3 3 3 2
         * 3 2 3 3
         * 3 3 3 2
         * 2 3 2 3
         *
         * 那么sum矩阵为
         * 0   0   0   0   0
         * 0   3   6   9   11
         * 0   6   11  17  22
         * 0   9   17  26  33
         * 0   11  22  33  43
         *
         * 计算matrix矩阵中左上顶点(i,j)到右下顶点(x-1,y-1)确定的田地的价值和
         *
         * 例如x=4,y=4,i=1,y=2,则
         * 返回值=sum[4][4]-sum[1][4]-sum[4][2]+sum[1][2]=43-11-22+6=16
         * 显然子矩阵(左上角顶点(1,2),右下角顶点(3,3))
         * 3 3
         * 3 2
         * 2 3
         * 的元素总和为16
         *
         * @param x
         * @param y
         * @param i
         * @param j
         * @param sum
         * @return
         */
        private static int getMaxValue(int x,int y,int i,int j,int[][] sum){
            return sum[x][y]-sum[x][j]-sum[i][y]+sum[i][j];
        }
    
    }

#### 效果： ####

4 4  
3332  
3233  
3332  
2323

我的座右铭：不会，我可以学；落后，我可以追赶；跌倒，我可以站起来；我一定行。