HDU 6695 – Welcome Party

题目链接:HDU 6695

题目要求把元素分成两个集合$A,B$,一个集合只能用$x$属性,另一个只能用$y$属性,要求$\min | \max A_i(x)- \max B_i(x) |$

以$x$属性为关键字进行排序(从小到大),从前往后枚举,假设第$i$个放在第一个集合里且是最大的,后面的元素就只能放在第二个集合里面。

讨论$B$集合中最大的元素是什么,假设$m$为$y[i+1 \cdots n]$的后缀最大值,如果$x_i \leq m$,那么一定是选择$m$,否则可以在前面的$y$当中选最接近$x_i$的,具体方法是在平衡树中二分。

这种固定一个求另一个的方法是一种常见方法。

 

说点什么

avatar
50
  Subscribe  
提醒