首页 > ACM题库 > HDU-杭电 > hdu 4384 King Kong II待解决[解题报告]C++
2015
05-24

hdu 4384 King Kong II待解决[解题报告]C++

King Kong II

问题描述 :

Have you seen the movie King Kong? If you have seen it, you must be impressed by the scene of the exciting fight between dinosaurs and King Kong, right? Though the dinosaurs have been fight off, King Kong has been injured very heavily. Considering that dinosaurs will come back very quickly, King Kong brings a lot of stones for fear that the dinosaurs attack again.
Now King Kong has arranged the stones at random in one line. But Different alignments of these stones would be different to King Kong. If the alignment is not the target in his mind, he will move the stones to their proper positions. Taking the physical consumption into consideration, King Kong could swap only two stones (whose weight is a and b weight units) at one time and for each time he will consume a+b thermal units. In order to minimize the physical consumption, King Kong should set a plan to move these stones. But this is too complex for king Kong and he needs your help.

输入:

There are several test cases. For each test case, it contains:
Line 1: One integer N (1<=N<=50000) which specifies the total number of stones.
Line 2: N integers (you are ensured that the absolute value of each integer is less than 216) which the weight of each stone initially. These numbers specify the initial stone alignment. There is a blank between two consecutive integers.
Line 3: N integers (you are ensured that the absolute value of each integer is less than 216 ) which the weight of each stone finally. These numbers specify the target alignment in King Kong’s mind. There is a blank between two consecutive integers.
The input will be ended by zero.

输出:

There are several test cases. For each test case, it contains:
Line 1: One integer N (1<=N<=50000) which specifies the total number of stones.
Line 2: N integers (you are ensured that the absolute value of each integer is less than 216) which the weight of each stone initially. These numbers specify the initial stone alignment. There is a blank between two consecutive integers.
Line 3: N integers (you are ensured that the absolute value of each integer is less than 216 ) which the weight of each stone finally. These numbers specify the target alignment in King Kong’s mind. There is a blank between two consecutive integers.
The input will be ended by zero.

样例输入:

3
3 2 1
1 2 3
3
1 2 3
1 2 3
4
4 2 1 2
1 2 2 4
4
8 1 2 4
1 2 4 8
5
1 8 9 7 6
1 6 7 8 9
0

样例输出:

Case 1: 4
Case 2: 0
Case 3: 8
Case 4: 17
Case 5: 41