笔试-度小满-180913
优质
小牛编辑
127浏览
2023-12-01
- 机器学习研发
- 选择 30,编程 2
火车站台
![](https://imgs.xnip.cn/cj/docimg/750/b0a64285-a230-4d2a-a7b3-af27cab6d60f.png)
![](https://imgs.xnip.cn/cj/docimg/750/018132df-8a7f-4185-b61b-06eb91e46ee3.png)
思路
- 求区间最大重叠数
暴力法(36%)
n = int(input())
tmp = dict()
mx = 0
for _ in range(n):
x, y = list(map(int, input().split()))
for i in range(x, y):
if i in tmp:
tmp[i] += 1
else:
tmp[i] = 1
mx = max(tmp[i], mx)
print(mx)
扫描线法(AC)
n = int(input())
tmp = []
mx = 0
for _ in range(n):
x, y = list(map(int, input().split()))
tmp.append((x, 1))
tmp.append((y, -1))
tmp.sort()
mx = 0
t = 0
for i in tmp:
if i[1] == 1:
t += 1
else:
t -= 1
mx = max(mx, t)
print(mx)
商品交易
![](https://imgs.xnip.cn/cj/docimg/750/27d38711-9815-4223-911f-423da7bcc344.png)
思路
- LeetCode原题
- 因为这里要求输出最小交易次数,所以贪心不可行,改用双指针
贪心(9%)
n = int(input())
nums = list(map(int, input().split()))
def foo(nums):
ans = 0
cnt = 0
if len(nums) <= 1:
return 0
for x in range(1, len(nums)):
if nums[x] - nums[x - 1] >= 0:
ans += nums[x] - nums[x - 1]
cnt += 2
return ans, cnt
ans, cnt = foo(nums)
print(ans, cnt)
双指针(AC)
n = int(input())
nums = list(map(int, input().split()))
def foo(nums):
ans = i = 0
cnt = 0
while i < len(nums):
while i < len(nums) - 1 and nums[i + 1] <= nums[i]:
i += 1
minima = nums[i]
i += 1
while i < len(nums) - 1 and nums[i + 1] >= nums[i]:
i += 1
if i < len(nums):
ans += nums[i] - minima
cnt += 2
return ans, cnt
ans, cnt = foo(nums)
print(ans, cnt)