编程介的小学生 2017-06-05 09:43 采纳率: 20.5%
浏览 989
已采纳

Minimal search cost

Problem Description
As we know, we need to spend O(n) time in the abstract finding a key(every two keys are different) in a non-sorted array. But if we make up a BST(binary search tree) before, then for each access, you need to spend log(N) time to do it. And for each access, there exists a road from the root node to the target node, whose length Ci is the number of the edges of the road.
Because there is an accessing frequency Fi for each key. And the total value of the tree is defined as following rule: SUM=Sigma(Ci*Fi), for i from 0 to N-1, N is the number of the keys. You need to find the minimal value M_SUM to make up a tree.

Input
There are a lot of cases. In each case, in the first line, there is an integer N to represent the number of keys. In the second line, there are N sorted integers Ki. In the third line, there are N integers Fi, which are the accessing frequency. 0<N<=1000, 0<=Fi<65536.

Output
For each case, just output the minimal search cost.

Sample Input
5
1 2 3 4 5
2 5 4 9 6

Sample Output
23

  • 写回答

1条回答 默认 最新

  • threenewbee 2017-06-24 16:44
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题
  • ¥20 在虚拟机的pycharm上
  • ¥15 jupyterthemes 设置完毕后没有效果