2013
12-23

# Minimal search cost

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.

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.

For each case, just output the minimal search cost.

5
1 2 3 4 5
2 5 4 9 6

23

1. /*
* =====================================================================================
*
* Filename: 1366.cc
*
* Description:
*
* Version: 1.0
* Created: 2014年01月06日 14时52分14秒
* Revision: none
* Compiler: gcc
*
* Author: Wenxian Ni (Hello World~), niwenxianq@qq.com
* Organization: AMS/ICT
*
* =====================================================================================
*/

#include
#include

using namespace std;

int main()
{
stack st;
int n,i,j;
int test;
int a[100001];
int b[100001];
while(cin>>n)
{
for(i=1;i>a[i];
for(i=1;i>b[i];
//st.clear();
while(!st.empty())
st.pop();
i = 1;
j = 1;

while(in)
break;
}
while(!st.empty()&&st.top()==b[j])
{
st.pop();
j++;
}
}
if(st.empty())
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}

2. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？

3. 为什么for循环找到的i一定是素数叻，而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak，而你每次取余都用的是原来的m，也就是n