方法一 暴力
将每辆巴士的服务范围存储起来, 每次查询时遍历所有巴士得到数量.
c++10ms, 数据太太太太弱, 暴力完全没有问题. 但是用Google Kickstart的原测试数据我是不相信能过的
时间复杂度为O(N*P), N为巴士数, P为查询次数
//
// Created by trudbot on 2022/6/23.
//
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<pair<int, int>> buses;
int T, N, P, C;
int l, r;
int i, j, k;
int count;
cin >> T;
for(i=1; i<=T; i++)
{
cin >> N;
for(j=0; j<N; j++)
{
cin >> l >> r;
buses.emplace_back(l, r);
}
cin >> P;
cout << "Case #" << i << ":";
while(P--)
{
count = 0;
cin>> C;
for(auto p : buses)
{
if(C>=p.first && C<=p.second)
count++;
}
cout << " " << count;
}
buses.clear();
cout << endl;
}
return 0;
}
方法二 差分
我们是否能通过这些巴士的服务范围而一次性得到所有城市的巴士数量呢
对一段序列{0, 0, 0, 0, 0}, 如果我们想让它第二到第四个元素都加个1, 我们可以让第二个元素+1, 第五个元素-1,得到{0, 1, 0, 0, -1}, 再对它求一遍前缀和, 就可以得到{0, 1, 1, 1, 0}. 这就是差分的基本思想
本题几乎是裸差分问题, 对于每个巴士的服务范围[l, r], 我们在差分数组中令count[l] += 1, count[r+1]-=1
即可, 最后将所有的巴士范围都插入到差分数组中后, 求一遍前缀和, 即为所有城市的巴士数量
时间复杂度:O(A), A为城市总数, 在题中固定为5000
//
// Created by trudbot on 2022/6/23.
//
#include <bits/stdc++.h>
using namespace std;
int main() {
int count[5010];
int T, N, P, C;
int i, j, k;
int l, r;
cin >> T;
for(i=1; i<=T; i++)
{
memset(count, 0, sizeof count);
cin >> N;
//构造差分数组
for(j=0; j<N; j++)
{
cin>> l >> r;
count[l]++;
count[r+1]--;
}
//求前缀和
for(j=2; j<=5001; j++) count[j] += count[j-1];
cin >> P;
cout << "Case #" << i << ":";
while(P--)
{
cin >> C;
cout << " " << count[C];
}
cout << endl;
}
return 0;
}
小于等于5001,为什么小于等于这一组测试数据输入的车站的最大值不行啊
不太能理解你的意思, 但查询的城市会是1~5000中任何一座
输入过程中找到最大车站编号,然后前缀和求到这个车站,后面的没有车经过,也就是默认的0,这样
这样是可以的, 不过要倒max + 1, 把cnt[r]–的影响消掉
哦哦,就是在max+1这个位置会多减,如果询问这个位置答案就是错的了,谢谢了
666
为什么数组要开5050
因为总共有5000座城市.
当然开5001就够了