华为OD机试真题 - 分配土地 (D卷,100分)

题目描述

从前有个村庄，村民们喜欢在各种田地上插上小旗子，旗子上标识了各种不同的数字。

某天集体村民决定将覆盖相同数字的最小矩阵形的土地分配给村里做出巨大贡献的村民，请问此次分配土地，做出贡献的村民种最大会分配多大面积?

输入描述

第一行输入 m 和 n，

• m 代表村子的土地的长
• n 代表土地的宽

第二行开始输入地图上的具体标识

输出描述

此次分配土地，做出贡献的村民种最大会分配多大面积

备注

• 旗子上的数字为1~500，土地边长不超过500
• 未插旗子的土地用0标识

用例

题目解析

1. 遍历整个地图，记录每个数字出现的次数。
2. 对于每个数字，计算其出现次数的一半（向下取整），即为该数字对应的矩阵形土地的边长。
3. 将所有数字对应的矩阵形土地的面积相加，即为做出贡献的村民种最大会分配的面积。

JavaScript算法源码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

void (async function () {
  class Rect {
    constructor() {
      this.minRow = Infinity;
      this.maxRow = -Infinity;
      this.minCol = Infinity;
      this.maxCol = -Infinity;
    }

    setRow(row) {
      this.minRow = Math.min(this.minRow, row);
      this.maxRow = Math.max(this.maxRow, row);
    }

    setCol(col) {
      this.minCol = Math.min(this.minCol, col);
      this.maxCol = Math.max(this.maxCol, col);
    }
  }
 
  const [m, n] = (await readline()).split(" ").map(Number);

  const rects = {};

  for (let i = 0; i < m; i++) {
    const nums = (await readline()).split(" ").map(Number);
    for (let j = 0; j < n; j++) {
      const num = nums[j];

      if (num > 0) {
        if (!rects[num]) rects[num] = new Rect();
        rects[num].setRow(i);
        rects[num].setCol(j);
      }
    }
  }

  let maxArea = 0;
  for (let num in rects) {
    const rect = rects[num];

    maxArea = Math.max(
      maxArea,
      (rect.maxRow - rect.minRow + 1) * (rect.maxCol - rect.minCol + 1)
    );
  }

  console.log(maxArea);
})();

Java算法源码

import java.util.HashMap;
import java.util.Scanner;

public class Main {
  static class Rect {
    int minRow = Integer.MAX_VALUE;
    int maxRow = Integer.MIN_VALUE;
    int minCol = Integer.MAX_VALUE;
    int maxCol = Integer.MIN_VALUE;

    private void setRow(int row) {
      this.minRow = Math.min(this.minRow, row);
      this.maxRow = Math.max(this.maxRow, row);
    }

    private void setCol(int col) {
      this.minCol = Math.min(this.minCol, col);
      this.maxCol = Math.max(this.maxCol, col);
    }
  }