Leading Robots 单调栈+排序

本文主要是介绍Leading Robots 单调栈+排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

链接：http://acm.hdu.edu.cn/showproblem.php?pid=6759.
来源：杭电多校第一场

题目描述

给n个机器人的初始位置p和加速度a，在无限长的跑道中，有多少机器人能成为领头羊。

分析

我们可以把所有机器人按照起始位置递减的顺序进行排序，然后建立一个栈。
我们尝试去扫描所有的机器人，如果他的加速度比上一个机器人大，那么他一定可以超过他成为领头羊，那么把它丢入栈中，并且计算一下这个机器人超过上上一个机器人的时间和上一个机器人超过上上一个机器人的时间，如果前者时间比后者短，说明前一个机器人还未成为领头羊，就已经被下一个机器人所超越，所以要弹出栈。
最后统计栈内元素个数，并且如果有两个机器人的位置和加速度相同的，那么他们无论什么时候都处于一个位置，也就是说他们都不可能成为领头羊，用一个map存一下即可

代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
#include <fstream>#include <cstring>#define debug(x) cout<<#x<<":"<<x<<endl;#define x first#define y second#define _CRT_SECURE_NO_WARNINGS#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")#pragma GCC option("arch=native","tune=native","no-zero-upper")#pragma GCC target("avx2")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> PII;
const int INF = 0x3f3f3f3f;
const int N = 50010;
int n;
struct Robots {double p,a;bool operator < (const Robots & t)const{if(p != t.p) return p > t.p;return a > t.a;}
}R[N];int main(){int T;scanf("%d",&T);for(int K = 1;K <= T;K++){map<Robots,int> M;scanf("%d",&n);for(int i = 1;i <= n;i++){scanf("%lf%lf",&R[i].p,&R[i].a);M[{R[i].p,R[i].a}]++;}sort(R + 1,R + n + 1);stack<Robots> Q;int sum = 0;for(int i = 1;i <= n;i++){sum++;if(Q.empty()){Q.push(R[i]);continue;}auto t1 = Q.top();int flag = false;while(1){if(R[i].a <= t1.a) break;if(R[i].p == t1.p){break;}Q.pop();flag = true;if(!Q.size()){Q.push(t1);break;}auto t2 = Q.top();if(R[i].a <= t2.a){Q.push(t1);break;}double T1 = (R[i].p - t2.p) / (t2.a - R[i].a);double T2 = (t2.p - t1.p) / (t1.a - t2.a);if(T1 <= T2){t1 = t2;}else{Q.push(t1);break;}}if(flag) Q.push(R[i]);}int ans = Q.size();while(Q.size()){auto t = Q.top();Q.pop();if(M[t] > 1) ans--;}printf("%d\n",ans);}return 0;
}