题目链接：点击查看
题目大意：n 个机器人在数轴上赛跑，给出每个机器人的起点和加速度，初始速度都为 0 ，问有多少个机器人在赛跑的过程中可以成为最前面的一个
题目分析：又是被zx学长秒掉的一道题，感谢zx学长的耐心讲解
首先根据高中物理知识，根据已知条件，可以得到位移与时间的方程 ，y 代表位移，x 代表时间，b 代表初始位置，k 代表加速度
因为都是抛物线，求交点非常的麻烦，因为我们只需要求交点的相对位置，所以可以将方程转换为位移与时间的平方的方程：，这样并不会影响交点的相对位置，同时将每一个位移曲线都转换为一条直线表示了
那么如何将机器人成为最前面的一个体现出来呢？将 n 条直线对应到平面直角坐标系中，将 x 轴从 [ 0 , inf ) 划分为无数个点，对于每个 x 而言，对应位置最上面的那条直线所代表的机器人，就是在 x 时刻最领先的机器人，所以我们只需要统计有多少条直线成为过最上面的直线就好了
按照斜率排序，就可以发现相邻的三条直线会出现下面两种情况：
我们将直线 i - 1 与直线 i 的交点记为 ( x1 , y1 ) ，将直线 i 与直线 i + 1 的交点记为 ( x2 , y2 ) ，发现当 x1 < x2 时，直线 i 所代表的机器人才有可能在最上面，而当 x1 >= x2 时，直线 i 完全被直线 i - 1 和直线 i + 1 所挡住，也就无法在最上面了
到此为止，我们就可以利用单调栈来实现上述模拟了，栈内维护的是都可以在最上面的直线，对于新遍历到的直线 i ，因为我们已经按照斜率递增了，显然单调栈内所有初始位置 b 小于当前直线的直线都是不符合条件的，如下图所示：
显然在上图中，st [ top ] 所代表的直线完全被第 i 条直线所覆盖
还有就是对于栈中的元素，将 st[ top - 1 ] , st[ top ] 和 i 这三条直线分别对应上文中的 i - 1 , i , i + 1 三条直线来比较交点的位置亦可以判断合理性
最后有个坑点，就是如果有两个机器人，起点和加速度都是相同的话，那么这两个机器人是不会对答案提供贡献的，这个可以用 map 判断一下
代码：
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=5e4+100;const double eps=1e-8;const double pi = acos(-1.0);int sgn(double x){if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1;
}struct Line
{LL k,b;bool operator<(const Line& t)const{if(k!=t.k)return k<t.k;return b>t.b;}
}line[N];int st[N],tp;double get_x(int i,int j)//y=k1x+b1,y=k2x+b2,前式减后式，得到x=-1.0*(b1-b2)/(k1-k2)，得到x的坐标
{return (-1.0*(line[i].b-line[j].b))/(1.0*(line[i].k-line[j].k));
}map<pair<LL,LL>,int>mp;int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;while(w--){mp.clear();int n;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%lld%lld",&line[i].b,&line[i].k);line[i].b*=2;//因为只需要求交点的相对位置，所以x和y轴同时放大两倍，避免出现1/2mp[make_pair(line[i].b,line[i].k)]++;}sort(line+1,line+1+n);tp=0;for(int i=1;i<=n;i++){if(line[i].k==line[i-1].k)//两直线平行 continue;while(tp&&line[i].b>=line[st[tp]].b)//如果当前直线在栈顶的直线上面，说明栈顶的直线不可能被看到 tp--;while(tp>1&&sgn(get_x(st[tp-1],st[tp])-get_x(st[tp],i))>=0)tp--;st[++tp]=i;}int ans=0;for(int i=1;i<=tp;i++){if(mp[make_pair(line[st[i]].b,line[st[i]].k)]==1)ans++;}printf("%d\n",ans);}return 0;
}
总结
以上是生活随笔为你收集整理的HDU多校1 - 6759 Leading Robots(单调栈)的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
