Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5140 --赛车
5140: 赛车
警告!
题目
状态
题解
题目描述
小爱和她的朋友小艾正在进行赛车游戏。她们从同一个起点,同一方向,同时出发。每个人在比赛中的速度可以被分为若干个**阶段**。在每个**阶段**里,小爱或小艾的速度是不变的。 由于车手的速度有变化,会出现**超车**的现象。所谓**超车**,就是指原本位置落后的一人,通过较快的速度实现了位置的超前。判定是否**超车**,关键看两人的相对位移是否从正变负(或从负变正)。在起点位置,因两人相对位置只是从 $0$ 变成了正数,所以不算发生**超车**。 给定小爱和小艾在每个**阶段**的速度和持续时间,请统计一下,在比赛的过程中,出现了多少次**超车**现象。
输入
第一行:两个整数 $n$ 和 $m$ + $n$ 表示小爱的赛车进程分为 $n$ 个阶段; + $m$ 表示小艾的赛车进程分为 $m$ 个阶段。 接下来 $n$ 行:每行表示小爱进程中的一个阶段,有两个整数 $t_i$ 和 $v_i$,表示该阶段中,小爱的速度为 $v_i$,持续时间为 $t_i$。 接下来 $m$ 行:每行表示小艾进程中的一个阶段,有两个整数 $s_i$ 和 $w_i$,表示该阶段中,小艾的速度为 $w_i$,持续时间为 $s_i$。 保证两人赛车的总距离是相等的,即保证 $$v_1t_1+v_2t_2+\cdots+v_nt_n=w_1s_1+w_2s_2+\cdots+w_ms_m$$
输出
单个整数:表示在整个比赛过程中,共计出现了多少次超车**现象**。
样例输入输出
输入#1
复制
2 3 10 10 2 50 4 15 8 15 1 20
输出#1
复制
1
提示
记 $L=v_1t_1+v_2t_2+\cdots+v_nt_n$, + 对于 $30\%$ 的数据,$1\leq n, m\leq 100$,$1\leq L\leq 10000$; + 对于 $60\%$ 的数据,$1\leq n, m\leq 1000$,$1\leq L\leq 10^7$; + 对于 $100\%$ 的数据,$1\leq n, m\leq 10^5$,$1\leq L\leq 10^9$;
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及+/提高-
标签
数学与数论
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
256 MB
来源
YACS2020年6月月赛乙组
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和