題目鏈接：點擊查看
題目大意：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(单调栈)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
