Leading Robots || 单调栈
题意：
一群机器人，已知它们的初始位置和加速度（初速度都为0），同时开始向右运动，求在无限长的时间内，有多少个机器人可以位于最前面（与别人同时为第一不算第一）。有可能有相同起始位置和加速度的机器人。
思路：
我们假设有一个机器人位置序列A、B、C......（A在B前，B在C前）。有两个栈，一个存追上的时间，一个存机器人。初始状态，把0push进时间栈，Apush进机器人栈。若B的加速度大于A，那么设tAB为追上的时间，tAB大于时间栈的栈顶元素0，那么把它入栈，同时把Bpush进机器人栈。若B的加速度小于A，那么肯定追不上，也就是说，B没有成为第一的可能了，就无需再考虑B了，那么接着考虑C（这里，我们忽略了加速度和位置相等的一系列需要特殊处理的情况，这些之后再说明）。假设tBC也大于时间栈的栈顶元素tAB，那么把tBC入时间栈，C入机器人栈。重复这个过程，假设一直到机器人E都满足这样的情况，即相邻的追赶时间一直递增，那么就一直push。为什么要push呢？因为tAB < tBC说明在C在追上B之前，B已经追上A了，说明B有可能成为第一。而若tAB > tBC，则说明在C追上B之前，B一直都没追上A，那么B就不可能当第一了。那么我们当然就要pop了！继续刚才的叙述，现在A-E已经顺利入栈，到了F，发现tDE > tEF，即在E追上D之前，F已经追上了E，那么E就不可能当第一了，我们就把Epop出去。当然，tDE也就要跟着pop出去了。这时，就相当于我们不再考虑E这个机器人了。现在栈顶是D和tCD。这时我们计算tDF。如果tCD > tDF，即在D追上C之前F已经追上D，那么D就不可能当第一了，我们就把Dpop出去，tCD也跟着pop出去。就这样，一路计算，一路pop，直至到某个栈顶元素i，我们就把Fpush进去，tiF也跟着push进去。这样，我们就形成了《单调栈》。时间栈是单调递增的，保证了相应的机器人栈里的元素都能当第一（最后还要排除与别人同时当第一的情况）。
于是，我们先把机器人按初始位置排序。位置在后面，加速度还比前面小的机器人不可能当第一，所以我们以加速度为第二关键字排序。
bug：
1）时间栈和u没开double；
2）双关键字排序，第二关键字不一定有序，所以加速度不一定是降序的，if条件漏写该判断；
3）结构体赋值可以整体赋值，而开始没有整体赋值，flag一直忘记赋过去了；
4）计算追赶时间的时候正负写反了；
5）栈的上届其实只需一个，然后刚开始遍历的时候上届还写错了；
6）按初始位置排序，p大的在前面，开始写反了；
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 7;
struct robot
{
int p, a;
bool flag;
}rb[maxn], rb2[maxn];
bool cmp(robot x, robot y)
{
if(x.p != y.p)
return x.p > y.p;
return x.a > y.a;
}
double t[maxn];
robot r[maxn];
int main()
{
int q;
scanf("%d", &q);
while(q--)
{
int n;
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
{
scanf("%d %d", &rb[i].p, &rb[i].a);
rb[i].flag = 0;
}
sort(rb + 1, rb + n + 1, cmp);
int cnt = 0;
for(int i = 1; i <= n; ++i)
{
if(i == 1)
{
rb2[++cnt] = rb[i];
continue;
}
if(rb[i-1].p != rb[i].p)
{
if(rb2[cnt].a >= rb[i].a) continue;
rb2[++cnt] = rb[i];
continue;
}
if(rb[i-1].a == rb[i].a)
{
rb2[cnt].flag = 1;
continue;
}
}
int ptm = 0, pr = 0, cur = 2;
t[++ptm] = 0, r[++pr] = rb2[1];
while(cur <= cnt)
{
double u = 2.0 * (r[pr].p - rb2[cur].p) / (rb2[cur].a - r[pr].a);
//cout << u << endl;
while(u <= t[ptm])
{
--ptm;
--pr;
u = 2.0 * (r[pr].p - rb2[cur].p) / (rb2[cur].a - r[pr].a);
}
r[++pr] = rb2[cur]; t[++ptm] = u;
++cur;
}
int ans = 0;
for(int i = 1; i <= pr; ++i) if(!r[i].flag) ++ans;
printf("%d\n", ans);
}
}