#cspj01001. 南华菌子的脱水处理

南华菌子的脱水处理

🍄 南华菌子的脱水处理

题目背景

楚雄南华县是著名的“中国野生菌之乡”。每年雨季,大量的野生菌被采摘下来,为了方便运输和保存,其中的 nn 筐菌子需要进行脱水烘干处理。

题目描述

现有 nn 筐新鲜野生菌,第 ii 筐菌子的“含水量”为 AiA_i。 工厂里有 nn 台不同功率的烘干机,由于天气和电力供应影响,第 jj 天烘干机的“能耗系数”为 BjB_j

已知:

  1. 每天只能处理一筐菌子。
  2. 处理一筐菌子的能耗 = 该筐菌子的含水量 AiA_i ×\times 当天烘干机的能耗系数 BjB_j

请问,如何安排每天处理哪一筐菌子,才能使得处理完这 nn 筐菌子的总能耗最小

输入格式

第一行包含一个整数 nn,表示菌子的筐数(也是天数)。 第二行包含 nn 个整数 A1,A2,,AnA_1, A_2, \dots, A_n,表示每筐菌子的含水量。 第三行包含 nn 个整数 B1,B2,,BnB_1, B_2, \dots, B_n,表示每天的能耗系数。

输出格式

输出一个整数,表示完成所有脱水工作的最小总能耗。

样例 #1

样例输入 #1

3
10 20 30
35 40 33

样例输出 #1

2090

提示与数据范围

【样例解释】

  • 第 1 天(能耗系数 35):处理含水量 20 的菌子,能耗 35×20=70035 \times 20 = 700
  • 第 2 天(能耗系数 40):处理含水量 10 的菌子,能耗 40×10=40040 \times 10 = 400
  • 第 3 天(能耗系数 33):处理含水量 30 的菌子,能耗 33×30=99033 \times 30 = 990
  • 总能耗:700+400+990=2090700 + 400 + 990 = 2090。这是所有方案中的最小值。

【数据范围】 对于 100%100\% 的数据,2n2×1052 \le n \le 2 \times 10^51Ai1051 \le A_i \le 10^51Bi1051 \le B_i \le 10^5