【Cf #299 C】Tavas and Pashmaks（单调栈，凸性）

一个经典的二维数点模型，如果某个人 $ x $ 两个速度都比另一个人 $ y $ 大，显然 $y$ 是不可能成为winner的。

但这里只考虑两个人$x$，$y$在两个属性各有千秋的时候，一定存在正整数$S$，$R$使得$x$，$y$都有可能成为winner。

这时考虑单调栈中顶端的两个人$a$和$b$，以及此时准备加入的人$c$，很明显当两两无法比较时，可能存在如下情况：

当$S$与$R$的比值小于一定值时，$a$总能胜$b$。
当$S$与$R$的比值大于一定值时，$c$总能胜$b$。

可以看到，当前者的阀值大于后者的阀值时，就不存在任何一组$S$和$R$，能使$b$成为winner了。（注：这里已经将人按照$s$值排了序）

前者的不等式大概长这样（当$a$能胜$b$）：

$ \frac{ s_{a} \, s_{b} \, ( r_{a} - r_{b} ) }{ r_{a} \, r_{b} \, ( s_{b} - s_{a} ) } > \frac{ S }{ R } $

后者的不等式大概长这样（当$c$能胜$b$）：

$ \frac{ s_{c} \, s_{b} \, ( r_{b} - r_{c} ) }{ r_{c} \, r_{b} \, ( s_{c} - s_{b} ) } < \frac{ S }{ R } $

将式子化简后就能判断$b$有没有win的可能性了。

这里简单证明为什么单调栈做可以不遗漏地剔除所有不合法的人：

在单调栈维护的过程中，保证了占中连续三个人之间是合法的。
也就是对于任意的 $x_{i }$，$x_{i+1}$，$x_{i+2}$，假设$x_{i}$能胜$x_{i+1}$的阀值是$v_{i}$，都有$v_{i} < v_{i+1}$，即合法的。
现在要证明对于在栈中的任意的$x_{i}$，$x_{j}$，$x_{k}$，其中$i < j < k$，都不能使$x_{j}$被剔除。

考虑另一种思路，可以将以上棘手的证明转化：

将每一个人的属性以$(\frac{1}{s_{i}}, \frac{1}{r_{i}})$的形式投射到坐标系上。答案$t = \frac{S}{s_{i}} + \frac{R}{r_{i}} = (S, R) \cdot (\frac{1}{s_{i}} + \frac{1}{r_{i}})$。

即在$(S,R)$方向上的投影。

对于任意一个$(S,R)$，在它上投影相等的点在一条垂直于它的直线上，该直线越靠近原点，投影长度越小。

枚举的任意一个$(S,R)$就相当于枚举了一条这直线，最先出现在直线平行线上的点就是winner。

显然，这个点在下凸壳上。并且可以得到，对于下凸壳上的每一个点都存在一组$(S,R)$使得其为winner。

而我们单调栈所做的就相当于自右下而左上地求出这样一个下凸壳。事实证明，两者的表达式是完全相同的。

$ \bigodot $ 技巧&套路：

单调栈的应用，单调栈剔除的变式。

 #include <cstdio>

 #include <set>

 #include <algorithm>

 typedef long long LL;

 const int N = ;

 struct No {

     int x, y, id;

     inline friend bool operator < (No a, No b) {

         return (a.x == b.x)? (a.y < b.y) : (a.x < b.x);

     }

 } p[N];

 int n, sta[N], top;

 std::set<No> S;

 inline int Check(No a, No b, No c) {

     return (LL) a.x * (a.y - b.y) * c.y * (c.x - b.x) > (LL) c.x * (b.y - c.y) * a.y * (b.x - a.x);

 }

 int main() {

     scanf("%d", &n);

     for (int i = ; i <= n; ++i) {

         scanf("%d%d", &p[i].x, &p[i].y);

         p[i].id = i;

     }

     std::sort(p + , p +  + n);

     for (int i = ; i <= n; ++i) {

         while (top >=  && p[sta[top]].y <= p[i].y) --top;

         while (top >=  && Check(p[sta[top - ]], p[sta[top]], p[i])) --top;

         sta[++top] = i;

     }

     for (int i = ; i <= top; ++i) {

         S.insert(p[sta[i]]);

     }

     top = ;

     for (int i = ; i <= n; ++i) {

         if (S.count(p[i])) sta[++top] = p[i].id;

     }

     std::sort(sta + , sta +  + top);

     for (int i = ; i <= top; ++i) {

         printf("%d ", sta[i]);

     }

     return ;

 }

巴特西

【Cf #299 C】Tavas and Pashmaks（单调栈，凸性）

最新文章

热门文章