关于第二十一次周常的附加题思路

没是的人

首先很感谢p叔办活动，再感谢认真的学出题，很有含量的题目辛苦了
附上第二十一次周常的传送门：http://rpg.blue/thread-328978-1-1.html
注意：这个帖子不能水，只能在周常总贴里水：http://rpg.blue/thread-276857-1-1.html
下面是
第二十一次周常附加题原题：

发奖金：
P叔决定给商店里两位表现优秀的员工发奖金。但是P叔发奖金的方式比较特别。
P叔共准备了2n份奖金，他把这2n份奖金分成n组。那么奖金就变成了：
a[0][0], a[0][1], a[1][0], a[1][1], a[2][0]......a[n-1][0], a[n-1][1]
每一组奖金是要两位员工分的。
以第一组奖金为例，第一位员工可以拿走a[0][0]，第二位员工则要拿走a[0][1]，或者相反。
由于两位员工都很优秀，所以，P叔想让他们获得的奖金总和的差值最小。
现在，请你帮忙计算，并将奖金总和的最小差值p出来。

（本题中：n<=150，每一份奖金的范围是1..300。
例：
n = 4
a = [[3,5],[7,11],[8,8],[2,9]]
答案：1
解释：差值最小的方案为
第一位员工拿3+7+8+9 = 27的奖金
第二位员工拿5+11+8+2 = 26的奖金，差值为1.）
——————————————————先来分析题意，懂题意的建议直接跳过———————————————
有许多人在周常发布以后表示不理解题意，这是一个传送门：490832999同学的理解。
提议解析传送门

下面我用一个更通俗的说法说：（误导向，把工资比喻成了苹果重量，可能越看越糊涂，慎入）
给甲乙两个人分苹果，苹果是一盒两个装的，共有n盒（n<150）
甲拿了盒子中的其中一个另一个就只能给乙了，直到拿完所有的苹果
拿完以后甲乙各自有一堆苹果了，怎么分配让两个人拿的苹果的总总量差值最小（不要吐糟苹果的重量范围1到300）

———————————————————————————————————————————————————
我试卷里的答案，先贴一下：

RUBY 代码复制

def extra
 
  n = rand(150)+1
  a  = []
  for i in 1..n
    a.push([rand(300)+1,rand(300)+1])
  end
    #p a    #--------生成的n份工资
  b = []
  for i in 0...n
    b[i] = (a[i][1]-a[i][0]).abs
  end
  b.sort!
    #p b    #--------每份工资的差值排序
  for t in 1..n-1
      b[-2] = (b[-2] - b[-1]).abs
    for i in 0..n-1
      if b[-2] <= b[i]
        b[i,0] = b[-2]
        break
      end
    end
    b.pop
    b.pop
    #print "t=" + t.to_s#-------循环次数，测试用
    #p b                #-------当次循环b结果，测试用
  end
  p b[0]
end

def extra


 


  n = rand(150)+1


  a  = []


  for i in 1..n


    a.push([rand(300)+1,rand(300)+1])


  end


    #p a    #--------生成的n份工资


  b = []


  for i in 0...n


    b[i] = (a[i][1]-a[i][0]).abs


  end


  b.sort!


    #p b    #--------每份工资的差值排序


  for t in 1..n-1


      b[-2] = (b[-2] - b[-1]).abs


    for i in 0..n-1


      if b[-2] <= b[i]


        b[i,0] = b[-2]


        break


      end


    end


    b.pop


    b.pop


    #print "t=" + t.to_s#-------循环次数，测试用


    #p b                #-------当次循环b结果，测试用


  end


  p b[0]


end

———————————————————————————————————————————————————


好的，现在题意也分析完了，答案也贴完了，下面是解题思路：（回归题意，工资，把比喻什么的都忘掉）
两份工资是有差值的，比如说[30,50]，他们的差值就是20，
不管怎么拿，甲拿了其中一份，乙就得拿另一份，所以这a[n]这一份工资分配完，甲乙工资的总量就差了20，无非是谁差谁的问题
那我们不妨把两组工资的所有差值都算出来：
            我们的原数组是这样的：a=[[a11,a12],[a21,a22],[a31,a32],...an[an1,an2]]
            新的差值数列构成单元就是：b1=a11-a12,a数组元素的里面两个元素的差值，bn=an1-an2
            得到新数组：b=[b1,b2,b3,...bn]

（更详细的解释，a=[[a11,a12],[a21,a22],[a31,a32],...an[an1,an2]]
上式可以化为：a=[[a12+b1,a12],[a22+b2,a22],[a32+b3,a32],...an[an2+bn,an2]]
在所有的工资份数都分配结束后，再把所有的a都约去，这样就是考虑那几个b在甲那里，那几个b在乙那里）


这样子做的话，问题就简化了不少，有原来的a数组（每个元素又是一个含有两个元素的数组）变成了简单的每个元素都是数字的数组
而且我们对b=[]里面的元素可以进行绝对值运算：bn=abs（bn），
因为本题不用告诉出题者具体怎么分配，而是只要p出差值就可以了，所以可以进行这样数据破坏性的处理。
于是在我们把所有的数据绝对值化了以后，就可以假设：最初的工资差值是0
要是甲拿了多的那份，甲乙的工资差值就是+=20，而乙拿的多的那份的话工资差值就是-=20

当这份分完我们就分下一份，下一份是+差值还是-差值呢，这要看怎么做更趋近于0，
当把所有的差值+完或者-完的时候，我们的工作也随之完成了

这是我最初的方案，已经很接近正确答案了，大体思路已经对了，但是还是有点小问题，继续说：
设差值x
for（j=0;j<n;j++）
if x<=0
  x+=b[j]
else
  x-=b[j]
end
把所有差值加减完就是最小差值吗？答案是错误的
在我连续的几次测试里，相同的数据，因为顺序不同，结果算出来的最小差值是不一样的
为什么会出现这样荒谬的情况？其实是我们在做最后这部前少了一个很关键的步骤。

最后交卷的18号考生wbsy8241同学就是这种思路，用p叔的话来说就是：
累加的下一个数组[x,y]（假设x>y），此时如果a>b就可以a+=y，b+=x。
p叔还专门举了一个例子来说明这个算法是错误的，详见成绩公布帖：http://rpg.blue/thread-331399-1-1.html

那正确的方法是怎么样的呢？，或者说缺少的关键步骤是什么呢？
缺少的步骤是，每次做要先选取最大的两个差值来计算
为什么每次要选取最大的差值来做呢？我们来模拟一下不这样做的一种情况：
比如n份工资的差值，前n-1份先计算好，最小的差值是1，而第n份的差值是10
这时候按照这种算法计算，总差值是1，是大于0的，那个下一个差值应该是：总差值-=这个差值
计算的答案是-9，反而变大了，要是再荒唐一点，最后一个差值是299，那个按这个计算方法计算出来的话会更大

而每次挑选数组b里最大的两个数字来比较得出新差值的话就避免了这个情况，
保证了，越计算到后面，参与运算的两个差值越小，不会出现突变的情况。

那么现在对于计算过程我们已经考虑完成了，我用人类语言来表述就是：
第一步：先把a数组里的数组里面的元素相减，得到一个差值数组b，
第二步：把b数组里的数字都绝对值处理，保证元素都是正数方便计算
第三步：再取b里面最大的两个值，并把他们从b里面删去，再把这两个值差值的绝对值放到b里（这样b的元素总量-2+1比原来少了一个）
第四步：重复第三步，直到b只剩下一个元素，跳到第五步
第五步：输出b里的这个值

如果每次运算都要找一堆数里的最大和第二大的值，势必很麻烦，所以我最后做汇编语言是这样写的：
def extra
  n = rand(150)+1
  a  = []
  for i in 1..n
    a.push([rand(300)+1,rand(300)+1])
  end#———————————————————————↑上面都是题目给的，↓下面开始自己编的
  b = []
  for j in 0...n
    b[j] = (a[j][1]-a[j][0]).abs#—————————————一二两步整合成一步
  end
  b.sort!#——————————————————————把b数组（差值数组）由小到大进行排序（数组的最后两个数字就是一堆数里的最大和第二大的值）
  for t in 1..n-1
      b[-2] = (b[-2] - b[-1]).abs
#b[-n]就是倒着数的第n个数字，这句的意思就是最大和第二大的值的差值的绝对值储存在b[-2]（为什么能进行破坏性数据运算的原因我前面已经讲过了）
    for j in 0..n-1#—————————————————把得到的新差值差到适当的位置，以保证b还是一个由小到大的数组。
      if b[-2] <= b[j]                                                     #（这个循环应该看得懂把，我不细细解释了，你要不嫌增加运算量可以每个循环都来个 b.sort!）
        b[j,0] = b[-2]#———————————————不常见用法说明：b[j,x] = 是把从第j个起的x个元素替换成后面的数组，F1里有。当x=0就是把后面的数组插入到第j个位置
        break
      end
    end
    b.pop#————————————————————pop的意思是删掉数组最后一个元素，连续执行两次就是“取b里面最大的两个值，并把他们从b里面删去”↑往上数14行
    b.pop
  end
  p b[0]#————————————————————最后把b里唯一的元素p出来，这个唯一的数字就是最终最小的差值。



程序再写一下：

RUBY 代码复制

def extra
  n = rand(150)+1
  a  = []
  for i in 1..n
    a.push([rand(300)+1,rand(300)+1])
  end
  b = []
  for i in 0...n
    b[i] = (a[i][1]-a[i][0]).abs
  end
  b.sort!
  for t in 1..n-1
      b[-2] = (b[-2] - b[-1]).abs
    for i in 0..n-1
      if b[-2] <= b[i]
        b[i,0] = b[-2]
        break
      end
    end
    b.pop
    b.pop
  end
  p b[0]
end

def extra


  n = rand(150)+1


  a  = []


  for i in 1..n


    a.push([rand(300)+1,rand(300)+1])


  end


  b = []


  for i in 0...n


    b[i] = (a[i][1]-a[i][0]).abs


  end


  b.sort!


  for t in 1..n-1


      b[-2] = (b[-2] - b[-1]).abs


    for i in 0..n-1


      if b[-2] <= b[i]


        b[i,0] = b[-2]


        break


      end


    end


    b.pop


    b.pop


  end


  p b[0]


end

反正这个程序才10来行，循环的次数也是很有限，应该是最简洁的答案了。


最后声明：本人语言表达是弱项，不要纠结文中语病，和浓郁的c语言风格编程格式，有什么问题可以问我，勿喷╮(╯▽╰)╭

最后@下出题人，这就是我的解题思路，站内信里我也说不清楚，只能开个帖子来告诉你了@认真的学

怪蜀黍

恭喜@没是的人 做对了附加题获得了好人卡。
这次的题目难度太大了，其实我没有想到会有人做对附加题。然而你的解答使我眼前一亮，语言明了而且有注解。经过我的多次数据测试，证明你的答案是正确的。
这篇论文很长很长，一定花了不少功夫来书写。感谢你把自己的思路和大家分享。水区不是我管理的版块，今天我没糖了，不能塞了喵。
对了，那个代码那里加个框，不然有【i】的地方后面就会变斜体字。

没是的人

好像没@上，再填装！发射——@认真的学 空格

怪蜀黍

好吧，第一@成功就行，@不成功再改也@不上了的。
其实有时看似没有@上，实际上他能收到的。
@认真的学  

Sunny.J

看不懂{:2_270:}

eve592370698

想不到楼主也开始做脚本，而且还是VX的，难道打算放弃地图不成吗？

没是的人

eve592370698 发表于 2013-9-9 12:49
想不到楼主也开始做脚本，而且还是VX的，难道打算放弃地图不成吗？

脚本我一直在学啊，这个是p叔的考题啦
地图，象以前那种xp大地图的风格比较少了，现在画vx，va的比较多

紫英晓狼1130

21有什么可研究的，就是方程，计算题
有时间研究27，28吧~

没是的人

紫英晓狼1130 发表于 2013-9-9 19:26
21有什么可研究的，就是方程，计算题
有时间研究27，28吧~

大雾啊，黑周常，查水表！
看p叔揍你╮(╯▽╰)╭