kth smallest weight

Revision en2, by Los_Angelos_Laycurse, 2017-05-18 10:31:30

There are N points cooridinate is x[1],x[2]....x[N]; try to partition these points into two sets {p1,p2,....pk1} (q1,q2,...qk2};p1<p2<..<pk1,q1<q2<..<qk2 the weight of partion w=abs(xp1)+abs(xp2-xp1)+abs(xp3-xp2)...+abs(xpk1-xp(k1-1)+abs(xq1)+abs(xq2-xq1)+...+abs(xqk2-xq(k2-1)).

find the kth smallest partion.. N<=10000, K<=500000, x[i]<=100000000..

you can submit this problem here:

http://www.lydsy.com/JudgeOnline/problem.php?id=3945

two partions are different if and only if the sets of them are different..

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English Los_Angelos_Laycurse 2017-05-18 10:31:30 76
en1 English Los_Angelos_Laycurse 2017-05-18 10:30:18 476 Initial revision (published)