2020多校1 - Leading Robots(单调栈)

标签: 个人题解  ACM  多校  单调栈

2020多校1 - Leading Robots(单调栈)

题面Leading Robots

题意:有 TT​ 个赛事,每个赛事中有 NN​ 个机器人准备在从左往右水平赛道上赛跑,已知每个机器人的初始位置 pip_i​ 以及加速度 aia_i​,初始速度为 00​,现假设赛道无限长的情况下有多少个机器人会在赛跑过程中处于过“领先”情况,某个机器人“领先”定义为该机器人在当前时刻 tt​ 跑在所有人前面且是唯一一个。

范围1T50;0<n5e4;0<pi,ai<2311 \le T \le 50;0 < n \le 5e4;0 < p_i, a_i < 2^{31}

分析: 我是这样思考的,由于初始位置以及加速度都是固定的,那么如果当前的领跑者 AA​ 被某个机器人 BB​ 超过了,那么之后 AA​ 永远都不可能再追上 BB​,因此我们只需要不断确定当前的领跑者会不会接下来被其他机器人追上。

暴力的方法是先根据机器人的初始位置升序以及加速度升序进行排序,那么排序后最后一个机器人就是当前的第一个领跑者,然后我们可以每轮对其后方的机器人求最小的相遇时间 t=min(2(pjpi)aiaj)t = min(\frac{2*(p_j-p_i)}{a_i-a_j}),如果 tt 的值合法,那么就让 jj 成为新的领跑者,计数器 +1+1,重复上述过程直至 tt 不合法。时间复杂度为 O(n2)O(n^2) ,显然是不行的。

另外我们需要考虑唯一性的问题,可以预处理出哪些机器人是重叠的,在计数的时候进行判断即可。

上述的暴力方法存在很多重复的计算,可以发现每次领跑者被超越的时间 tt​ 总是单调递增的,考虑使用单调栈来进行优化。

在这里插入图片描述

根据上面的路程-时间图像,线条已经进行了排序(a3a_3​ > a2a_2​),若没有线条 44​,那么 1,2,31,2,3​ 轮流成为领跑者。现在出现了 44​,先考虑线条 2,3,42,3,4​,由于 44​22​ 相遇的时间早于 33​22​ 的相遇时间,那么 33​ 无论如何都无法领跑,剩下再考虑线条 1,2,41,2,4​,由于 44​11​ 的相遇时间早于 22​11​ 的相遇时间,那么 22​ 无论如何都无法领跑,这样的过程与单调栈的出栈入栈操作是一致的。

具体方式:

若栈大小 <3< 3,直接将线条压栈。

否则取出栈顶三个元素 a,b,ca, b, ccc​ 在底部),

aacc 的相遇时间小于等于 bbcc 的相遇时间,那么将 bb 出栈,重复上述过程(此时说明 aa 会早于 bb 遇到 ccbb 由于加速度劣势永远追不上,成为不了领跑人);

否则结束操作(此时满足领跑时刻单调递增)。

Code

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;

inline int read()
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

const int MAXN = 5e4 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double eps = 1e-9;
const double PI = acos(-1.0);

int n;

struct Node
{
    int p, a;
    bool operator<(Node other) const
    {
        if (p == other.p)
            return a < other.a;
        else
            return p < other.p;
    }
} nodes[MAXN];

stack<int> st;

int vis[MAXN];

signed main()
{
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    int T = read();
    while (T--)
    {
        memset(vis, 0, sizeof(vis));
        while (!st.empty())
            st.pop();
        n = read();
        for (int i = 0; i < n; i++)
        {
            nodes[i].p = read(), nodes[i].a = read();
        }
        sort(nodes, nodes + n);
        // 预处理重叠的机器人
        for (int i = 1; i < n; i++)
        {
            if (nodes[i].p == nodes[i - 1].p && nodes[i].a == nodes[i - 1].a)
            {
                vis[i] = vis[i - 1] = 1;
            }
        }
        for (int i = n - 1; i >= 0; i--)
        {
            // 先入栈一个
            if (i == n - 1)
            {
                st.push(i);
            }
            else
            {
                int pre = st.top();
                // 若位置相同,或者加速度较小,绝对无法追上
                if (nodes[i].p == nodes[pre].p || nodes[i].a <= nodes[pre].a)
                {
                    continue;
                }
                // 栈中至少要有两个元素
                if (st.size() == 1)
                {
                    st.push(i);
                }
                else
                {
                    while (st.size() > 1)
                    {
                        st.pop();
                        int prepre = st.top();
                        st.push(pre);
                        // 计算出两个相遇时间
                        double t1 = 2.0 * (nodes[prepre].p - nodes[pre].p) / (nodes[pre].a - nodes[prepre].a);
                        double t2 = 2.0 * (nodes[pre].p - nodes[i].p) / (nodes[i].a - nodes[pre].a);
                        // 满足单调,退出
                        if (t1 < t2)
                        {
                            break;
                        }
                        else
                        {
                            // 栈顶机器人永远追不上,丢弃
                            st.pop();
                        }
                        pre = st.top();
                    }
                    // 找到位置安心放下
                    st.push(i);
                }
            }
        }
        // 统计唯一的领跑人
        int ans = 0;
        while (!st.empty())
        {
            int x = st.top();
            st.pop();
            if (!vis[x])
                ans++;
        }
        cout << ans << endl;
    }
    return 0;
}

【END】感谢观看

版权声明:本文为qq_41765114原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41765114/article/details/107602571

智能推荐

一致性hash算法

散列(hash)在我看来就是一个数组,而与数组不同的点在于数组是按顺序写入的,而hash是按照一定的hash算法确定元素在数组中的位置的。hash最难的问题在于会有冲突出现,如果两个object根据相应的hash算法得出的值一样便产生了hash冲突。在所有解决hash冲突的方法中,我最欣赏的是链式解决法,即将hash到同一位置的元素用链表连接。当然还有其它几种处理hash冲突的算法,比如建立公共溢...

OpenCV-Python learning-1.安装,图片读取显示

1. OpenCV与OpenGL区别 https://www.zhihu.com/question/20212016 一个是让机器识别东西的,OpenCV是给电脑做眼睛的。 一个是让机器计算出更好画面的,OpenGL用在游戏渲染方面很多。 OpenCV(Open Source Computer Vision Library)是一个基于(开源)发行的跨平台计算机视觉库,OpenGL(全写Open G...

Mycat+Mysql分布式架构改造和性能压力测试

架构实现 Mycat作为数据库高可用中间件具备很多的功能,如负载均衡,分库分表,读写分离,故障迁移等。结合项目的实际情况,分库分表功能对于关联查询有很高的要求,需要从业务角度考虑分库分表后的关联查询SQL的分析,业务代码动作较大,所以在此方案中我们不考虑分库分表。主要应用Mycat的负载均衡及故障迁移的功能即可。 整个架构改造包括两个部分,第一是单例Mysql改为多个Mysql,同时负载均衡,并且...

人脸识别之疲劳检测(二)阈值法、KNN分类和K-means聚类

Table of Contents 1、均值法 2、中值法 3、KNN 4、K-means 结合上一节在获得人眼特征点后需要对睁眼闭眼状态做出判断,方法的选择需要经验结合公平的评价方法,使用大量测试集得到不同方法下的精确度并做出比较: 1、均值法 50帧睁眼数据取均值,得到不同阈值下精确度。 2、中值法 50帧睁眼数据取中值,得到不同阈值下精确度。 3、KNN KNN是一种ML常用分类算法,通过测...

CodeForce Tic-Tac-Toe

Two bears are playing tic-tac-toe via mail. It's boring for them to play usual tic-tac-toe game, so they are a playing modified version of this game. Here are its rules. The game is played on the foll...

猜你喜欢

Python雾里看花-抽象类ABC (abstract base class)

首先认识模块 abc,python中没有提供抽象类与抽象方法,然而提供了内置模块abc来模拟实现抽象类,例如提供泛映射类型的抽象类 abc.MutableMapping 继承abc.MutableMapping构造一个泛映射类型(类似python中的dict) 当然继承abc.Mapping 也可以,毕竟MutableMapping是其子类 dict是python中典型的映射类型数据结构,其接口的...

python 文件操作

2, with open (‘xx.txt’,‘w’,encoding=‘utf-8’) as f: f.write(‘文件内容或对象’)...

【Python基础】使用统计函数绘制简单图形

机器学习算法与自然语言处理出品 @公众号原创专栏作者 冯夏冲 学校 | 哈工大SCIR实验室在读博士生 2.1 函数bar 用于绘制柱状图 2.2 函数barh 用于绘制条形图 2.3 函数hist 用于绘制直方图 直方图与柱状图的区别 函数pie 用于绘制饼图 2.5 函数polor 用于绘制极线图 极线图是在极坐标系上绘出的一种图。在极坐标系中,要确定一个点,需要指明这个点距原点的角...

css:顶部按钮固定,上面内容滑动

这种需求我们平时见到很多的,实现方法也多的参差不齐,下面我说一种简单的。如图: 可以看到只有红线部分滚动,底下按钮是固定的。 代码...

环形公路堵车概率模型(含详细解析)

文章目录 基础理论 代码实现 图形分析 基础理论 路面上有n辆车,以不同的速度向前行驶, 模拟堵车问题。 有以下假设: 假设某辆车的当前速度是v。 若前方可见范围内没车,则它在下一秒的车速提高到v+1,直到达到规定的最高限速。 若前方有车,前车的距离为d,且d < v,则它下 一秒的车速降低到d-1 。 每辆车会以概率p随机减速v-1。、 代码实现 图形分析 图形中颜色越重的地方,说明很多车...