首页 > 试题广场 >

火车站台

[编程题]火车站台
  • 热度指数:1717 时间限制: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

输入

4
4 7
2 6
2 5
1 2

输出

3
并查集,但是有问题,大佬们谁能指点一波    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)
题目什么意思?
发表于 2019-10-23 16:25:53 回复(0)
没有看懂题意额,是说站点的最大的运营量吗
发表于 2019-09-26 10:51:49 回复(1)
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)
@amphi17, @sky游荡  两位给的方法真的牛,我看了好久才get到,自己做了一个示意图,放下面大家参考一下
发表于 2022-05-12 16:45:09 回复(1)
#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)
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)
差分数组
#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 回复(0)
看了别人的代码才理解。
题目的意思是有若干条线路,每条线路起点--终点间的(起点不算)站台都会停靠,每条线路都走一次,求停靠次数最多的站台。
暴力求解是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)
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)