Algorithmic Engagements 2010 Sweets

http://main.edu.pl/user.phtml?op=showtask&task=cuk&con=PA2010
这题目的意思是。。。有N个物品,N<=24,重量<=10^9,分成3堆。。
设3堆重分别为A,B,C且A<=B<=C,求C-A的最小值。。。
看到这个N<=24并且分成3份不难想到要折半搞了。。
考虑前N/2和后N/2个物品的两个方案,
设前N/2的物品的方案是(a1,b1,c1),

后N/2的物品的方案是(a2,b2,c2)
那么。。由于和是固定的。。只要考虑两个。。不妨考虑a和c。。
设S为所有物品和
那么a1+a2<=S-(a1+a2+c1+c2)
<=>(a1*2+c1)+(a2*2+c2)<=S
S-(a1+a2+c1+c2)<=c1+c2
<=>(a1+c1*2)+(a2+c2*2)>=S
设F(x)=ax*2+cx,G(x)=ax+cx*2,T(x)=cx-ax
也就是说F(1)+F(2)<=S,G(1)+G(2)>=S,求最小的T(1)+T(2)。。
这是个傻叉问题。。。排序降维之后直接数状数组就好了>_<。。。

5 thoughts on “Algorithmic Engagements 2010 Sweets

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>