首页 > 试题广场 >

火车站台

[编程题]火车站台

热度指数：1796 时间限制：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

输入

输出

算法知识视频讲解

ac_q

并查集，但是有问题，大佬们谁能指点一波 13.3333%。。。。

#include <iostream> 
#include <vector>
#include <set>
using namespace std;


vector<int> parent(100000);
vector<int> ranks(100000);
int max_ = 1;
void init(int n)
{
	for (int i = 0; i < n; i++)
	{
		parent[i] = i;
		ranks[i] = 1;
	}

}
int find(int root)
{
	if (parent[root] != root)
	{
		return parent[root] = parent[parent[root]];
	}
	else
		return parent[root];
}
void union1(int a, int b)
{
	if (find(a) == find(b))
		return;
	else
	{
		if (ranks[a] < ranks[b])
		{
			parent[find(a)] = parent[find(b)];
			ranks[b] += ranks[a];
		}
		else
		{
			parent[find(b)] = parent[find(a)];
			ranks[a] += ranks[b];
		}
		max_ = max(max_, max(ranks[a], ranks[b]));
	}
}
int main()
{
	int n = 0;
	cin >> n;
	vector<vector<int>> vv(n, vector<int>(2, 0));
	init(100000);
	for (int i = 0; i < n; i++)
	{
		cin >> vv[i][0] >> vv[i][1];
		union1(vv[i][0], vv[i][1]);
	}
	cout << max_  - 1<< endl;
	system("pause");
}

发表于 2020-06-06 00:14:04 回复(0)

OFFER_HXJ

没有看懂题意额，是说站点的最大的运营量吗

发表于 2019-09-26 10:51:49 回复(1)

acqierement...

import java.util.*;

public class Main {

    /**
     题目关键是【它在沿途的所有城市都会停靠（显然不包括起点Yi，但是包括终点Xi）】
     2到5表示3，4，5都会有一个站台，最后求站台数量最多的一个点。
     解题思路：主要是起点和终点，记录起点2，然后3，4都是1，5终点就减一变成0，
     这样子其实变成了【包括起点，不包括终点】，题意是【不包括起点，包括终点】，
     形式变了一点，但是最后结果也是一样的
     */
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[] city = new int[100001];
        for (int i = 0; i < n; i++) {
            int x = input.nextInt();
            int y = input.nextInt();
            city[x]++;
            city[y]--;
        }
        int count = 0;
        int res = 0;
        for (int i = 1; i < city.length; i++) {
            count+= city[i];
            res = Math.max(res, count);
        }
        System.out.println(res);
    }
}

发表于 2020-03-17 14:57:23 回复(0)

yjiedu

@amphi17, @sky游荡两位给的方法真的牛，我看了好久才get到，自己做了一个示意图，放下面大家参考一下

发表于 2022-05-12 16:45:09 回复(1)

昔遥暮云

题目什么意思？

发表于 2019-10-23 16:25:53 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,x,y,t=0,Max=0;
    cin>>n;
    int a[100003];
    memset(a,0,sizeof(a));
    while(n--){
        cin>>x>>y;
        a[x]++;
        a[y]--;
    }
    for(int i=1;i<=100000;i++){
        t += a[i];
        Max = max(Max, t);
    }
    cout<<Max<<endl;
    return 0;
}

发表于 2019-10-19 11:36:22 回复(0)

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)

第一次来多多包涵

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class TrainStation {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();//输入行数
        int[][] path = new int[n][2];
        for (int i=0; i<n; i++){
            path[i][0] = input.nextInt();
            path[i][1] = input.nextInt();
        }
       /* for (int i=0; i<n; i++){
            for (int j=0; j<2; j++){
                System.out.print(path[i][j]);;
            }
        }*/
        HashMap<Integer, Integer> stationNums = new HashMap<>();
        for (int i=0; i<n; i++){
            while (path[i][0] < path[i][1]){
                if (stationNums.containsKey(path[i][0])){
                    stationNums.put(path[i][0], stationNums.get(path[i][0]) + 1);
                    path[i][0]++;
                }else {
                    stationNums.put(path[i][0], 1);
                    path[i][0]++;
                }
            }
        }
        int maxValue = Integer.MIN_VALUE;

        for (Map.Entry<Integer, Integer> entry : stationNums.entrySet()) {
            int value = entry.getValue();
            if (value > maxValue) {
                maxValue = value;
            }
        }
        System.out.println(maxValue);
    }
}

给出HashMap的方式

发表于 2023-06-28 03:25:15 回复(0)

徐云哲

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[1000001];
        for(int i = 0; i < n; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            while(x < y) {
                arr[x]++;
                x++;
            }
        }
        int max = 0;
        for(int i : arr) {
            max = Math.max(i, max);
        }
        System.out.println(max);
    }
}

编辑于 2022-08-31 09:53:05 回复(0)

nlping

差分数组

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int cf[100005]= {0};
    //memset(cf, 0, sizeof(cf));
   
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        cf[x]++;
        cf[y]--;
    }
    int ans  = 0,sum = 0;
    for(int i=1;i<=100005;i++){
        sum +=cf[i];
        if(sum > ans){
            ans = sum;
        }
    }
    cout<<ans;
    return 0;
}

发表于 2020-09-04 17:20:42 回复(0)

羡慕啊

#include <bits/stdc++.h>

using namespace std;

int main() {
    long long n;
    cin >> n;
    // 线路区间可以表示为：[x,y)，左闭右开，终点站闭、起始站开
    // a数组如何理解？
    // 从左向右遍历数组，如果遇到一个线路的终点站，
    // 那么从这一站开始，之后的站台都要运营这条线路，
    // 直到遇到了这条线路的起始站，之后的站台就不再运营这条线路
    // 多条线路叠加后，用a数组来表示每个线路的起点和终点
    // 某一条线路的终点为i，a[i]就加一，起点为j，a[j]就减一
    // 从左到右遍历时，用变量curr表示当前站需要运营的线路
    // 从走到i站台开始，curr就加一
    // 走到j站台时，这条线路不需要运营了，curr就减一
    vector<int> a(1e5 + 1, 0);
    int left, right;
    for(long long i = 0; i < n; i++) {
        cin >> left >> right;
        a[left]++;
        a[right]--;
    }
    int curr = 0, ans = 0;
    for(int i: a) {
        curr += i;
        ans = max(ans, curr);
    }
    cout << ans << endl;
    return 0;
}

发表于 2020-08-09 12:37:04 回复(1)

sky游荡

看了别人的代码才理解。

题目的意思是有若干条线路，每条线路起点--终点间的（起点不算）站台都会停靠，每条线路都走一次，求停靠次数最多的站台。

暴力求解是O(mn)肯定是过不了的，看了别人的代码才感慨自己的菜。

思路:设置一个数组来标记每一个站台，

每次将起点位置的下一个位置（因为起点不算）加一，终点的下一个位置减一。

这样做只需要一次遍历一次数组，求和相加，取最大值就好了。

举个例子:如果就有一条线路1-4，那么标记数组count的第2个位置为1，第5个位置为负一，遍历求和到第二个位置，和第4个位置之间都是1，说明站台能被停靠1次。而第5个位置为-1，到了就会被减去，后面求和出来就是0了。大概是这个意思，多条线路的情况画画就明白了。

n = int(input())
count = [0]*100001
for i in range(n):
    tmp = list(map(int,input().split()))
    count[tmp[0]+1] += 1
    count[tmp[1]+1] -= 1
comp = 0
res = 0
for i in range(len(count)):
    comp += count[i]    
    res = max(res,comp)
print(res)

发表于 2020-04-07 20:03:17 回复(5)

Amphi17

n=int(input())
route=[]
for i in range(n):
    route.append([int(i) for i in input().split()])
dp=[0 for _ in range(100001)]
for each in route:
    dp[each[0]]+=1
    dp[each[1]]-=1
count=0
max_num=0
for i in dp:
    count+=i
    max_num=max(max_num,count)
print(max_num)

发表于 2019-08-17 14:50:38 回复(2)