1 Star 1 Fork 0

bensonrachel/Atcoder_algorithm

加入 Gitee
与超过 1200万 开发者一起发现、参与优秀开源项目,私有仓库也完全免费 :)
免费加入
文件
该仓库未声明开源许可证文件(LICENSE),使用请关注具体项目描述及其代码上游依赖。
克隆/下载
TPM(step1)C. Number of Equal.py 2.13 KB
一键复制 编辑 原始数据 按行查看 历史
bensonrachel 提交于 2021-08-11 20:35 . 双指针专题 step1 三题
# -*- coding: utf-8 -*-
# @project : 《Atcoder》
# @Author : created by bensonrachel on 2021/8/11
# @File : TPM(step1)C. Number of Equal.py
# https://codeforces.com/edu/course/2/lesson/9/1/practice/contest/307092/problem/C
def TPM():
cnt = []
tag = 0
p1 = 0# 第一个数组的指针
p2 = 0# 第二个数组的指针
while (p1 < n and p2 < m):# 都还没遍历完。
if (rate_a[p1] <= rate_b[p2]):# 当前数组一的数小于等于数组二的数
if (rate_a[p1] == rate_b[p2]):# 看是否是等于的情况,就加一
tag += 1
p1 += 1# 指针往后移一位
else:# 当前数组一的数大于数组二的数
cnt.append(tag)# 可以把tag的值传入数组。
tag = 0 # 然后归零
p2 += 1 # 然后指针往后移动一位
while (p2 < m and rate_b[p2] == rate_b[p2 - 1]):
cnt.append(cnt[p2 - 1])
p2 += 1
"""
发现后面的值跟前面一样的话就直接移动指针往数组里放相同的值就行
"""
if (p2 < m):# 数组一遍历完了。
# 说明数组二还有数没计算,因为以第二个数组为基准去数第一个数组。
# 但是如果数组二遍历完,就不用管数组一有没有遍历完了
# 数组二还有数:
if (tag != 0):# 说明数组二与数组一最后的数有匹配但是还没放进数组,就先放进数组
cnt.append(tag)
for i in range(p2 + 1, m):# 然后从下一个遍历数组二,看有没有和前面的一样的,有的话往数组里放相同的值就行
if (rate_b[i] == rate_b[i - 1]):
cnt.append(cnt[i - 1])
else:# 遇到一个不一样的说明后面的不会有了,可以停了
break
return sum(cnt)
"""
自己的做法:以第二个数组为基准去数第一个数组。
"""
if __name__ == "__main__":
n, m = map(int, input().split())
rate_a = [int(i) for i in input().split()]
rate_b = [int(i) for i in input().split()]
res = TPM()
print(res)
Loading...
马建仓 AI 助手
尝试更多
代码解读
代码找茬
代码优化
1
https://gitee.com/bensonrachel/atcoder_algorithm.git
git@gitee.com:bensonrachel/atcoder_algorithm.git
bensonrachel
atcoder_algorithm
Atcoder_algorithm
master

搜索帮助