官方题解——校车
校车
http://www.nowcoder.com/questionTerminal/0e5ee062c6c547049086b62b8967acf7
G - 校车
出题人的标程有问题,我验题居然没发现,是我验题不认真了,背锅。。。
抛开题目出锅,这个题目还是蛮简单的,出题人给的做法是离散化+差分,我现场写了个更加暴力的。本来是打算作为签到题之一的没想到演了各位大佬了,谢罪。
出题人标程:
#include<bits/stdc++.h> using namespace std; int road[100005][2]; int num[2000005]; set<int>all; map<int,int>mp; int main() { int T; cin >> T; while(T--) { memset(num,0,sizeof(num)); memset(road,0,sizeof(road)); all.clear(); mp.clear(); int n; cin >> n; for(int i = 1; i <= n; i++) { cin >> road[i][0] >> road[i][1]; all.insert(road[i][0]); all.insert(road[i][1]); } // 离散化 int an=0; for(auto it=all.begin();it!=all.end();it++) { an++; mp.insert(pair<int,int>(*it,an)); } // 差分 for(int i=1; i <= n; i++) { int l=mp[road[i][0]]; int r=mp[road[i][1]]; num[l]++; num[r]--; } int sum=0,mx=0; for(int i = 1; i <= 2 * n; i++) { sum+=num[i]; mx=max(mx,sum); } cout << all.size() << " " << mx << endl; } return 0; }
我的代码:
#include <bits/stdc++.h> #include <cstring> using namespace std; int T, n, a[100005], b[100005]; set<int> s; map<int, int> up, down; int ans1=0, ans2=0; int main() { scanf("%d", &T); while(T--) { ans1=0; ans2=0; s.clear(); up.clear(); down.clear(); scanf("%d", &n); for (int i=1; i<=n; ++i) { scanf("%d%d", &a[i], &b[i]); s.insert(a[i]); s.insert(b[i]); up[a[i]]++; down[b[i]]++; } int t=0; // 暴力算 for (auto it=s.begin(); it!=s.end(); ++it) { t+=up[*it]; t-=down[*it]; ans2=max(ans2, t); } ans1=s.size(); printf("%d %d\n", ans1, ans2); } return 0; }