[补题记录] Atcoder Beginner Contest 294（E）

本文主要是介绍[补题记录] Atcoder Beginner Contest 294（E），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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;
}

这篇关于[补题记录] Atcoder Beginner Contest 294（E）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---