贝壳找房 · 计算几何 · 算法编程题
贝壳找房 计算几何 n ≤ 1e5 时限 1 秒 / 128 MB

题目描述

牛牛有 n 对黑色的木棍,长度分别为 a_1,a_2,...,a_n , n 对白色的木棍,长度分别为 b_1,b_2,...,b_n ,牛牛可以每次取走一对黑色的木棍和一对白色的木棍组成一个对边颜色相同,临边颜色不同的矩形,并计算出这个矩形的面积。每对木棍只能使用一次且不能将这对木棍拆开,牛牛能知道他能得到的所有矩形的总面积最大为多少。

输入输出

输入描述
第一行,一个整数 n(1≤ n ≤ 10^5) 。
第二行, n 个整数 a_1,a_2,...,a_n(1≤ a_i≤ 10^5) 。
第三行, n 个整数 b_1,b_2,...,b_n(1≤ b_i≤ 10^5) 。
输出描述
输出一行一个整数表示牛牛能得到的所有矩形的总面积最大为多少。

样例共 1 组

样例 1
输入
5
1 5 2 4 3
3 1 1 2 1
输出
29

算法解析依据一般

考点:计算几何

数据规模 n ≤ 1e5 | 限制 1 秒 / 128MB | 标准输入输出

题目画像

  • 数据规模:n ≤ 1e5
  • 元素值域:a_i ≤ 1e5,b_i ≤ 1e5(注意整数类型选择,避免溢出)
  • 复杂度门槛:只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 源站时限:1 秒(牛客口径,非本题专属门槛)

解题思路

参考方向:计算几何

把几何关系转成坐标运算,用整数运算避免浮点误差。

思路框架(计算几何 通法 · 非本题专属)

  1. 把点、向量、线段用坐标表示。
  2. 几何判定(平行、垂直、共线、相交)尽量用叉积/点积的整数形式:叉积为 0 即共线。
  3. 距离用平方比较,避免开方带来的浮点误差。
  4. 面积用叉积(鞋带公式)计算。

实现要点:叉积 cross = x1*y2 - x2*y1;用它判断顺时针/逆时针和共线。

复杂度:时间 O(n) ~ O(n²) | 空间 O(n)

该范式的通法易错点

  • 用浮点相等判断几何关系(应用整数叉积)。
  • 没考虑三点共线、重合等退化情况。

对照本题

  • 数据规模 n ≤ 1e5,只允许 O(n log n) 及更优,朴素 O(n²) 会超时。
  • 元素值域最大到 1e5 —— 求和 / 相乘时记得开 64 位整数。
本题在源数据中没有官方考点标签,方向由题面特征推断,仅供参考。

样例

样例 1

  • 输入:5 / 1 5 2 4 3 / 3 1 1 2 1
  • 输出:29

解析由校招宝本地引擎整理(依据源站考点标签 / 人工判题标注 / 题面规模信号),非官方题解,仅供思路参考。

本题来源:贝壳找房2023届校招算法卷3。

‹ 上一题 全部编程题 下一题 ›
编程算法题为只读内容:无需作答,直接看题与解析 · 本站不提供在线判题 · 解析由校招宝本地引擎整理,非官方题解