题目描述
一条街道可以看作一个数轴。
街道上住着 n 个居民并设有 m 个垃圾桶,每个居民的住所或垃圾桶占据一个位置。
已知,这 n+m 个位置两两不同。
每个居民每天都会前往距离自己家最近的垃圾桶处倒垃圾。
如果这样的垃圾桶不唯一,则居民会优先选择前往位置坐标更小的垃圾桶处倒垃圾。
请你计算,对于每个垃圾桶,每天有多少居民在该垃圾桶处倒垃圾。
输入格式
第一行包含两个整数 n,m。
第二行包含 n+m 个整数 x1,x2,…,xn+m,表示所有居民住所以及垃圾桶的位置坐标。
第三行包含 n+m 个整数 t1,t2,…,tn+m,如果 ti=1,则表示第 i 个位置坐标处是垃圾桶,如果 ti=0,则表示第 i 个位置坐标处是居民住所。
输入保证,满足 ti=1 的 i 的数量为 m。
输出格式
不妨按照位置坐标从小到大的顺序,将 m 个垃圾桶编号 1∼m。
请你在一行中输出 m 个整数 a1,a2,…,am,其中 ai 表示每天在第 i 个垃圾桶处倒垃圾的居民数量。
样例
数据范围
前三个测试点满足 1≤n,m≤5。
所有测试点满足 1≤n,m≤105,1≤x1<x2<…<xn+m≤109,0≤ti≤1。
输入样例1:
3 1
1 2 3 10
0 0 1 0
输出样例1:
3
输入样例2:
3 2
2 3 4 5 6
1 0 0 0 1
输出样例2:
2 1
输入样例3:
1 4
2 4 6 10 15
1 1 1 1 0
输出样例3:
0 0 0 1
算法
先算出两个垃圾桶的中间值作为区间端点,然后判断有几个居民楼在区间内。
时间复杂度
排序O(nlogn)
双指针O(n + m)
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10;
const int INF = 1e9 + 10;
int n,m;
int x[N],a[N],b[N],t[N],cnt[N];
struct Range
{
int l,r;
}ranges[N];
int main()
{
cin >> n >> m;
for(int i = 1;i <= n + m;i++)
{
cin >> x[i];
}
int cnt1 = 0,cnt2 = 0;
for(int i = 1;i <= n + m;i++)
{
cin >> t[i];
if(t[i]) a[++cnt1] = x[i];
else b[++cnt2] = x[i];
}
sort(a + 1,a+m+1);
sort(b + 1,b+n+1);
int l = -INF,r = INF;
for(int i = 1;i <= m;i++)
{
if(i != m)
{
r = (a[i] + a[i + 1]) >> 1;
ranges[i] = {l,r};
l = r;
}
else
{
ranges[i] = {a[i],INF};
}
}
for(int i = 1,j = 1;j <= m;)
{
while(b[i] <= ranges[j].r && i <= n) cnt[j]++,i++;
printf("%d ",cnt[j]);
j++;
}
return 0;
}