0%

度小满编程记——火车站台问题

发表于 更新于 阅读次数： Valine：
本文字数： 423 阅读时长 ≈ 1 分钟

​

​ 思路：这道题讲道理如果起点终点没有那么大就很简单了，直接使用字典进行存储，然后选择value最大的那个值即可。而这道题目中明显直接使用上面的思路是行不通了，因此这题使用了一种比较巧的方式，

​ 先将各个列车的起点终点分别编码为(站点,编号)，起点编号为-1，终点编号为0，然后从小到大对元组进行排序，然后便利元组列表，如果是终点，那么将维护数+1，如果是起点，那么代表到这里已经有一辆车不再需要维护了，同时记录最大的维护值，便利完全部列表最大的维护值即为结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
n = int(input())
train = []
t = 0
ans = 0


for i in range(n):
	l = list(map(int,input().split()))
  train.append((l[0],1))
  train.append((l[1],-1))

train.sort()   #这里是关键点，sort函数将对元组进行排序

for i in train:
  if i[1]==0:
    t+=1
  else:
    t-=1
    ans = max(ans,t)
pritn(ans)

上式中的sort函数对元素为元祖的列表来进行排序，默认规则是先使用元组的第一个元素进行排序，当第一个元素值相同时再使用第二个元素进行排序，下面是一个例子：

1
2
3
4
5
l = [[1,1],[2,1],[2,-1],[1,-1]]
l.sort()

output:
	[[1, -1], [1, 1], [2, -1], [2, 1]]

在这个问题中使用sort进行排序后，表示由于同一个车站的负值被排在前面，每次先减去1，也就是前一个车一这里为起点，不需要再使用维护。

之前还遇到过好多类似的问题，其实都可以采用这种类似的思路来减少内存占用，比如之前360笔试中遇到过的找