贪心-P1565-牛宫

r囧r小猫 2023-07-15 15:19 38阅读 0赞

## 题目描述 ##

AP 神牛准备给自己盖一座很华丽的宫殿。于是，他看中了一块 N×M 的矩形空地。空地中每个格子都有自己的海拔高度。AP 想让他的宫殿的平均海拔在海平面之上（假设海平面的高度是0，平均数都会算吧？）。而且，AP 希望他的宫殿尽量大，能够容纳更多的人来膜拜他。请问AP 的宫殿最后会有多大？  
**输入格式**  
第一行为 N 和 M 。之后 N 行，每行 M 个数，描述的空地的海拔。  
**输出格式**  
输出宫殿最大面积。  
**样例**  
**输入**

3 2
    4 0
    -10 8
    -2 -2

**输出**

## 奇怪的是这道题没给到数据范围！！ ##

import java.util.Scanner;
    public class Main {
        
        static long n, m, ans, area;
        static int top;
        static long sta[] = new long[100000];
        static long kn[] = new long[100000];
        static long s[][] = new long[210][210];
        static long a[][] = new long[210][210];
        static long f2[][] = new long[210][210];
    
        public static long fn(long x) {
        
            int l = 1, r = top, ans1 = -1;
            int mid;
            while (l <= r) {
        
                mid = (l + r) / 2;
                if (sta[mid] < x) {
        
                    r = mid - 1;
                    ans1 = mid;
                } else l = mid + 1;
            }
            return ans1;
        }
        public static void main(String[] args) {
        
            Scanner scanner = new Scanner(System.in);
            n = scanner.nextInt();
            m = scanner.nextInt();
            for (int i = 1; i <= n; i++) {
        
                for (int j = 1; j <= m; j++) {
        
                    a[i][j] = scanner.nextInt();
                    s[i][j] = a[i][j] + s[i][j - 1];
                }
            }
            for (int i = 1; i <= m; i++) {
        
                for (int j = i; j <= m; j++) {
        
                    area = 0;
                    sta[0] = 0;
                    top = 0;
                    for (int k = 1; k <= n; k++) {
        
                        area += s[k][j] - s[k][i - 1];
                        if (area > 0) ans = Math.max(ans, (j - i + 1) * k);
                        else {
        
                            long num = fn(area);//矩阵和
                            if (num != -1) ans = Math.max(ans, (j - i + 1) * (k - kn[(int) num]));
                            //找到了新矩阵所包含的大于0的矩阵才更新
                            if (area < sta[top]) {
        
                                sta[++top] = area;//记录area<0的值
                                kn[top] = k;//同时记录该矩阵的长
                            }
                        }
                    }
                }
            }
            System.out.println(ans);
        }
    }

## 考点： ##

矩阵的关系，还有谁说牛宫一定是矩形的。