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;
}
京公网安备 11010502036488号