HDU - 6759 Leading Robots（单调栈）

传送门

Reference：https://blog.csdn.net/qq_44828887/article/details/107499606

首先需要明确的三点是：

• 加速度较大者可能当第一
• 位置靠前者可能当第一
• 重复的起点和加速度的机器人不可能当第一

明显，加速度是衡量当第一的第一标准，位置是第二标准。按照加速度升序处理，加速度相同按起点升序处理，这样排序之后，依次入栈。每次入栈时需要考虑：如果后面的机器人起点大于栈顶起点（其加速度是肯定大于等于栈顶），那么就需要不断出栈直到不满足为止。如果栈内有超过两个机器人，当前机器人设为 $L3$，那么每次考虑栈顶机器人 $L2$和栈顶前一个机器人人 $L1$。设初始位置为 $b$加速度为 $k$， $x=\frac{1}{2}t^2$根据位置和加速度的关系有 $y=kx+b$，是过 $y$轴的直线，如下图所示：

$L1,L2$的相交关系是固定的（不满足的已经出栈），那么 $L3$只有图中的蓝线和红线两种情况，显然蓝线是不满足的，因为它在 $L2$即将超过 $L1$翻身做老大之前已经超过了 $L2$，那么这时需要将 $L2$也就是栈顶元素剔除，重复这个过程直到不满足为止

最后答案就是栈内的元素个数？还不是，因为还没考虑重复的起点和加速度的机器人，需要遍历栈得到答案

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=5e4+10;struct hash_pair{template <class T1, class T2>size_t operator()(const pair<T1, T2>& p) const{auto hash1 = hash<T1>{}(p.first);auto hash2 = hash<T2>{}(p.second);return hash1 ^ hash2;}
};struct node{int p,a;
}d[maxn];int st[maxn],head;
unordered_map<pii,int,hash_pair> mp;bool cmp(node &x,node &y){if(x.a==y.a) return x.p<y.p;return x.a<y.a;
}bool crocmp(node L1,node L2,node L3){return 1LL*(L3.p-L2.p)*(L1.a-L3.a)-1LL*(L3.p-L1.p)*(L2.a-L3.a)<=0;
}inline bool check(int x){if(head>0 && d[st[head]].p<=d[x].p) return 1;return 0;
}inline bool judge(int x){if(head<=1) return 0;if(crocmp(d[st[head-1]],d[st[head]],d[x])) return 1;return 0;
}int main(){//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);//ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t,n;scanf("%d",&t);while(t--){mp.clear(),head=0;scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&d[i].p,&d[i].a);pii cur=mkp(d[i].p,d[i].a);mp[cur]++;}sort(d+1,d+1+n,cmp);for(int i=1;i<=n;i++){while(check(i) || judge(i)) head--;st[++head]=i;}ll ans=0;for(int i=1;i<=head;i++){pii cur=mkp(d[st[i]].p,d[st[i]].a);if(mp[cur]>1) continue;ans++;}printf("%lld\n",ans);}return 0;
}