巧用map:西安邮电大学第五届ACM-ICPC校赛（同步赛）G 校车（比原题解简单多了）

本文主要是介绍巧用map:西安邮电大学第五届ACM-ICPC校赛（同步赛）G 校车（比原题解简单多了），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

原题链接：https://ac.nowcoder.com/acm/problem/206077

分析：此题给数据范围10^9,如果用数组，会内存超限，需要用map离散化储存数据，可以将站点作为map的键，map的值储存本站上下车人数，而map还会对键自动排序，因此从头遍历map就相当于模拟校车从第一站出发一直到最后一站，同时定义变量sum记录校车上的人数，把每个map值加到sum里相当于模拟每一站的上下车，然后用stu_num记录车上人数的最多的时候即可。

#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
int main(){int T,i,j,k,n,x,y;cin>>T;while(T--){mp.clear();cin>>n;for(i=1;i<=n;i++){cin>>x>>y;mp[x]++;mp[y]--;}int num_stop=0,num_stu=0,sum=0;for(auto it=mp.begin();it!=mp.end();it++){num_stop++;sum+=it->second;num_stu=max(sum,num_stu);}cout<<num_stop<<" "<<num_stu<<endl;}
}

这篇关于巧用map:西安邮电大学第五届ACM-ICPC校赛（同步赛）G 校车（比原题解简单多了）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---