首页 > 试题广场 >

火车站台

[编程题]火车站台

热度指数：1776 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

在Z省，有若干个个城市坐落在一条直线上，从左到右依次标号1,2,3,…，其中每个城市有一个火车站点，现今已经开放了n条火车路线，第i条火车路线是从第Yi个城市到第Xi个城市，因为Z省地势奇特，标号小的城市地势较低，所以火车是从高往低开的，再通过神秘力量传送回高地，即Yi一定大于Xi，它在沿途的所有城市都会停靠（显然不包括起点Yi，但是包括终点Xi），火车停靠就需要火车站台来运营维护。火车站台随着运营线路的数量不同，其损耗速度、维护成本也各异，现在我们想知道所有站台中，所运营的线路数最大是多少。

输入描述:

第一行一个数n。（1≤n≤100000）

接下来n行每行两个数Xi和Yi，分别代表第i条火车路线的终点和起点。（1≤Xi<Yi≤1e5）

输出描述:

共一行，一个非负整数，表示最大运营路线数。

示例1

输入

输出

算法知识视频讲解

Python3

TS9527

数学描述题目：在一个全0的数组上有n次操作，每次操作使得该数组下标在(x_i, y_i]范围内的所有元素+1，求最后这个数组当中最大的元素。

解法：差分

class MainActivity:

    def main(self):
        # Read the data
        n = int(input())
        diffs = [0] * int(1e5 + 1)
        # Traverse
        for _ in range(n):
            x, y = map(int, filter(lambda x: len(x) > 0, input().split(' ')))
            diffs[x] += 1
            diffs[y] -= 1
        result = 0
        cache = 0
        for diff in diffs:
            if diff:
                cache += diff
                result = max(result, cache)
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-31 13:45:54 回复(0)