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