主页 / 问题 / 1597987
Accepted
Fynjy
Asked:2024-10-27 23:29:42 +0000 UTC2024-10-27 23:29:42 +0000 UTC

关于围栏的问题

  • 772

帮助彼得找到两根栅栏，它们与道路一起形成一个面积最大的矩形区域，并打印这个面积。

所有部分的宽度相同且等于 1。

输入（转到标准输入）

程序的输入是一行，其中包含一个整数数组length，其中length[i]是第 i 个栅栏的长度。换句话说，数组的第 th 个元素以从到 的i线段形式指定栅栏，其中是道路。(i, 0)(i, length[i])0

而且0 ≤ length[i] ≤ 10 000，栅栏的数量也n满足条件2 ≤ n ≤ 100 000。

我们测试的所有输入数据始终遵循指定的参数，不需要额外的检查。

输出（预期为标准输出）

一个整数，形成的面积的最大面积。

实施例1

输入：

2 4 3 2 1 4 1

结论：

16

在第一个示例中，最大的区域形成在长度为 4 的两个栅栏之间。

实施例2

输入：

1 2

结论：

1

在此示例中，第二个栅栏未使用其整个长度，因为我们只对矩形区域感兴趣。

我的代码：

line = input()
length = [int(item) for item in line.split()]
max_area = 0
if length[0] > 0 and length[1] > 0:
    max_area = 1
for left in range(0, len(length) - 1):
    for right in range(left + 1, min(left + 1 + length[left], len(length))):
        min_length = min(length[left], length[right])
        width = right - left
        if min_length == width:
            max_area = max(max_area, min_length * width)
print(max_area)

测试通过了。但答案是错误的。程序的输出与预期不符。这有什么问题吗？

python

2 个回答

  1. Best Answer

    您的程序并不总是正确计数。例如，对于输入，100, 100它将返回 1，尽管正确答案是100。

    我怀疑这件作品：if min_length == width:。为什么需要它？

    如果条件被删除，则上面的示例开始被视为正确。下一个例子：2 1 1 2.程序的答案是 2，正确答案是 6。

    这一次受到怀疑min(left + 1 + length[left], len(length))。为什么需要第一个参数min？

    如果min您替换第二个参数，程序将开始正确计数。

    程序中还有一些可以纠正和简化的地方，但它计算正确，只是速度慢。尽管这是一个单独问题的主题。

    • 2

  2. 迭代数组的每个元素（最后一个元素除外），我们从右侧（在嵌套循环中）迭代每个元素，并将面积计算为所得栅栏对的最短长度与栅栏之间距离的乘积他们（指数的差异）。我们返回最大的结果。

    JS 代码。

    function findMaxArea(input_arr){
    let max_area = 0;
  
    for(let i=0; i < input_arr.length-1; i++){
        for(let j=i+1; j < input_arr.length; j++){
            max_area = Math.max(max_area, (j-i)*Math.min(input_arr[i], input_arr[j]));
        }
    }
  
    return max_area;
}

console.log(findMaxArea([1,2]));
console.log(findMaxArea([2,4,3,2,1,4,1]));

    更理性的版本。我们同时从阵列的两端出发。初始最大面积：两端长度的最小值与数组长度的乘积 - 1。我们正在寻找更大的选项，从两端向中间移动，直到左右两端靠得更近。

    我们从栅栏长度最短的一侧开始移动（如果相等，先向右，然后保持方向）。一旦该方向有更长的栅栏，我们就重新计算面积并保存最大的结果。

    function findMaxArea(arr) {
  let l = 0;
  let r = arr.length - 1;

  let max_area = Math.min(arr[l], arr[r]) * (r - l);

  let longest_left = arr[l];
  let longest_right = arr[r];
  let to_right = longest_left <= longest_right;

  while (r - l > 1) {
    if (to_right) {
      l++;
      if (arr[l] <= longest_left) {
        continue;
      } else {
        longest_left = arr[l];
        if (longest_left > longest_right) {
          to_right = false;
        }
      }
    } else {
      r--;
      if (arr[r] <= longest_right) {
        continue;
      } else {
        longest_right = arr[r];
        if (longest_right > longest_left) {
          to_right = true;
        }
      }
    }
    max_area = Math.max(max_area, Math.min(arr[l], arr[r]) * (r - l));
  }

  return max_area;
}

console.log(findMaxArea([1, 2]));
console.log(findMaxArea([2, 4, 3, 2, 1, 4, 1]));

    • 1

相关问题