3735 - 平分
描述

考虑足球比分系统,一场足球比赛从开始到结束的过程中,摄像机随机拍摄了 n 张比分信息,问你本场比赛最多出现了几次平分。

例如:3 个比分信息为 2:0、3:1、3:4,最终比分为 3:4,所以最多只可能出现最初的 0:0 以及 3:3 这 2 次平分。如果只有 1 张 3:4,那么最多可能有 0:0、1:1、2:2、3:3 共 4 次平分。

输入

第一行一个数 n。
接下来 n 行,每行两个数 a[i], b[i],表示第 i 次拍摄时比分为 a[i]:b[i]。
最后一次拍摄的比分即为最终比分。
n <= 10000,a[i], b[i] <= 10^9,a[i], b[i] 保证不降。

输出

输出最多平分次数,包括开局的 0:0。

样例

输入

3
2 0
3 1
3 4

输出

2
提示

相邻两个比分 (pa, pb) 到 (a, b) 之间可能出现的平分为 k:k,其中 max(pa, pb) <= k <= min(a, b)。注意若起点本身就是平分(pa == pb),它在上一段已被计数,不能重复计入;开局 0:0 先计入答案。

因此每段可新增的平分次数为:pa == pb 时 max(0, min(a,b) - max(pa,pb));pa != pb 时 max(0, min(a,b) - max(pa,pb) + 1)。逐段累加即可,复杂度 O(n)。

来源
51nod 2540
标签
题目参数
Time Limit 1 second
Memory Limit 128 MB
提交次数 2
通过次数 1