好些日子没来论坛了.大家中秋节快乐!!!


版主大人的这个问题,我也用数学方法归纳了一下,下面是我的思路(没时间写代码):
我分析其中一组数据:
样例输入：
10
8     2
98    1
100   54
999   3
2     1
53    9
100   99
77    66
23    22
99    92

输出：
2673
 


考虑到  力气=Wi-Vi+Wj-Vj；并且合并i,j两堆书后W= Wi+Wj，V=Vi+Vj
我们可以用  book[i] = Wi-Vi;来保存数据，也不要分别保存W和V的值。

这样上面的数据就可以这样保存 book[10]={6,97,46,996,1,44,1,11,1,7}；
下面来分析：   前面... a b c d e f ...A B C D E F ... 后面
这样，我们用两个变量，一个从前面开始，一个从后面开始，
 1。当这两变量还未相遇时，
    (1):前面开始的变量，如果有 a <= c,那么a和b是一定可以合并的；
    (2):后面开始的变量，如果有 A >= C,那么C和B是一定可以合并的；
    (+):由上面，我们可以把book数组变成了；    (6+97)=103,46,996,1,44,1,11,8=(1+7),共用的力气是 103+8=111 【book=_103,46,996,1,44,1,11,8_】
                                              (103+46),996,1,44,1,11,8           ,共用的力气是103+46=149 【book=_149,996,1,44,1,11_,8】
                                              149,996,1,44,(1+11),8              .共用的力气是  1+11=12  【book=149,_996,1,44,12,8_】
                                              149,996,1,44,(12+8)                ,共用的力气是  12+8=20  【book=149,996,_1,44,20_】，这里不再满足这个条件了
 2。当1。不再满足了，那么我们只要考虑这两个变量交界处的情况了，
                                              149,996，(1+44),20                 ,共用的力气是  1+44=45  【book=149,996,45,20】
 3。2。的步骤以后，这时候就执行和1。相反步骤，变量向两边散开去，
                                              149,996,(45+20)                    ,共用的力气是 45+20=65  【book=149,996,65】
                                              148，(996+65)                      ,共用的力气是996+65=1061【book=149,1061】
 4。重复1~3的步骤，最后当3中book只有2个数的时候，退出循环。

现在我们来计算总力气：【149+1061】+1061+65+45+20+12+149+111 = 2673



上面有些细节我没仔细考虑，我想按照这个思路是应该可以找到解决方法的。
还有就是，如果有 W的值比V的大的话，那解决起来更简单，连移动数组元素都不要。但好像楼主给出的测试数据中有些数据并不这样。

[ 本帖最后由 Windy0Winll 于 2010-9-22 17:24 编辑 ]

实在感谢！具体代码你觉得怎么实现？

呵呵，我没想过要怎么写，只是觉得这样倒有可能是一个可行的思路，大家可以按照这个思路想一个比较好的办法解决此题。
如果这个方法可行的话，那它的时间复杂度应该也是log(n)级别的。

你的思路遇到下面的样例：

样例输入：
100
1000 1
1000 999
1000 1
768 24
245 9
837 765
349 208
985 34
65 4
230 120
1000 1
1000 1
1000 999
1000 999
99 98
84 75
231 123
954 239
248 111
111 11
356 12
1000 1
1000 1
1000 999
1000 1
1000 353
1000 1
942 1
39 1
23 21
9 12
5 999
999 10
340 203
13 2
874 873
804 710
734 248
249 112
935 24
248 24
358 45
937 27
275 256
57 2
567 56
657 2
869 37
367 267
257 247
457 75
853 57
346 57
87 38
367 38
427 98
194 92
924 53
247 1
1000 99
1000 32
64 21
134 245
235 23
975 42
246 2
463 461
426 75
439 24
429 24
96 2
45 1
349 10
220 44
276 42
256 10
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1
1000 999
1000 1

book[]数组中会出现 ...........,1,999,1,999,1,999,1,999,1,999,1,999,1,999,1,999.......的时候好像就很麻烦了！有什么好办法没？？

book[i]=Wi-Vi我想这一步，不管用什么方法都一样，反正在求力气的时候，Wi和Vi都是成对出现，所以我们只要保存它的差值。

999，1,  999,1,999,  1,999,  1,999,1,  999,1
对于这样的数据，也并不是很麻烦；
如果就上面这几个数的话，按照规则来：
     (999+1),999,1 , 999,1 , 999,1,   999,1 , (999+1)
->    1000, 999,1,   999,1,  999,1,   999,1,  1000
      1000, (999+1), 999,1,  999,1,  (999+1), 1000
->    1000, 1000,    999,1,  999,1,  1000,    1000
      1000, 1000,    (999+1) (999+1) 1000,    1000
->    1000,  1000,   1000,   1000,   1000,    1000
      1000,  1000,   (1000+1000)     1000,    1000
->    1000   1000     2000      1000    1000
      (1000+1000)    2000   (1000+1000)
->      2000    2000   2000
->          4000 2000
->            60000


好象和普通数据都是一样的，没什么区别


也有可能我在想某个问题的时候想错了。






[ 本帖最后由 Windy0Winll 于 2010-9-22 20:39 编辑 ]

留下QQ一起讨论

3，3，2，3，99，3，2，3，3
3，3，2，3，2，3，2，3，199，3，2，3，2，3，2，3，3
这两组数据，你处理起来有什么技巧？？

ps：版主及各位，我的QQ 42206900 希望可以加好友一起讨论此问题！！

[ 本帖最后由 jack10141 于 2010-9-22 21:57 编辑 ]

斑竹都来了……

呵呵，找到这个问题的来源了！这个问题是动态规划中的“最小代价子母树”问题！楼主及各位可以参考ppt文件：

哦，谢谢，先下来看看