4480. 倒垃圾

垃圾"/>

4480. 倒垃圾

一条街道可以看作一个数轴。

街道上住着 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

分析：正反遍历了一遍登机了每个居民最近的垃圾桶编号，再遍历一遍统计每个垃圾桶的居民数量，最后输出

代码如下：

#include <iostream>using namespace std;
const int N=2e5+10;
int a[N],t[N],b[N],ans[N];
int n,m;
int main()
{cin>>n>>m;for(int i=1;i<=n+m;i++)cin>>a[i];for(int i=1;i<=n+m;i++)cin>>t[i];int cnt=0;for(int i=1;i<=n+m;i++){if(t[i])cnt=i;else b[i]=cnt;}cnt=0;for(int i=n+m;i;i--){if(t[i])cnt=i;else{if(!cnt)continue;if(!b[i])b[i]=cnt;else{if(a[cnt]-a[i]<a[i]-a[b[i]])b[i]=cnt;}}}for(int i=1;i<=n+m;i++){if(t[i])continue;ans[b[i]]++;}for(int i=1;i<=n+m;i++){if(!t[i])continue;cout<<ans[i]<<" ";}return 0;
}