URL:https://atcoder.jp/contests/abc294
目录
E
Problem/题意
Thought/思路
Code/代码
E
Problem/题意
我们将其当作一个铺路的过程。
给总长度 L,计划 1 有 N 步,计划 2 有 M 步,每一步给出(v,l),意为在接下来的 l 长度中,每一单位的值都为 v。
问这两个计划,有多少个单位的值是相同的。
Thought/思路
模拟题,主要是要想清楚每次如何更新答案。
我们可以维护当前走到了计划的第几步、计划的总路程、上一步计划的总路程。
当我们处于某一个状态时,一定是当前两者的总路程中取一个小的,以及上一步计划的总路程里取一个大的,相减就是应该加上的答案。
Code/代码
#include "bits/stdc++.h"#define int long longint l, n, m, ans;struct node {int v, l;
}t1[100007], t2[100007];signed main() {std::cin >> l >> n >> m;for (int i = 1; i <= n; ++ i) std::cin >> t1[i].v >> t1[i].l;for (int i = 1; i <= m; ++ i) std::cin >> t2[i].v >> t2[i].l;int s1 = 0, s2 = 0;int l1 = 0, l2 = 0;int p1 = 0, p2 = 0;while (p1 <= n and p2 <= m) {if (s1 == s2) {s1 += t1[++ p1].l;s2 += t2[++ p2].l;} else if (s1 > s2) {s2 += t2[++ p2].l;} else if (s2 > s1) {s1 += t1[++ p1].l;}if (t1[p1].v == t2[p2].v) ans += std::min(s1, s2) - std::max(l1, l2);if (s1 > s2) {l2 = s2;} else if (s1 < s2) {l1 = s1;} else if (s1 == s2) {l1 = l2 = s1;}}std::cout << ans;
}