题目描述
思路
其实就是思维题，题意很简单，找到一个居民左侧和右侧（如果存在的话）的垃圾桶中最近的那个垃圾桶，然后让那个垃圾桶的计数器加一。
从题目中挖掘的性质：左侧的垃圾桶就是居民左侧位置最大的那个，而右侧的垃圾桶就是居民右侧的位置最小的那个。由于题目给定垃圾桶的位置升序（即使无需我们也可以排序），很容易想到二分，我们只需要枚举每个居民，然后两次二分分别找到左侧和右侧的垃圾桶的位置就可以了。
但是这里有很多时间优化（一次二分其实就可以）和细节问题（二分边界处理--哨兵）。
一次二分：
由于右侧的那个垃圾桶是居民右侧位置最小的垃圾桶，那么该垃圾桶的前一个垃圾桶一定是居民左侧位置最大的垃圾桶（如果存在的话）。
哨兵
前面一直提到，如果垃圾桶存在的话。是因为存在两种边界情况：（题目给定垃圾桶至少一个。）
- 一个居民位于所有垃圾桶的左侧，因此不存在它右侧的垃圾桶。
- 一个居民位于所有垃圾桶的右侧，因此不存在它左侧的垃圾桶。
所以说为了二分的时候简单一些，我们可以分别在最左侧和最右侧设置两个哨兵。
但是这两个哨兵的位置该取多少呢？这个最好不要凭空想象。
我们可以从二分的语句里面去观察：由于我们需要比较左侧垃圾桶和右侧垃圾桶到居民的距离那个更小。
即：\(right - cur\) 与 \(cur - left\) 的那个值更小。
当我们处于边界情况的时候，我们肯定不希望取到我们的哨兵。所以说：
- 处于边界情况1，即不存在右侧的垃圾桶，此时 \(right\) 取得哨兵的值，假设为 \(val\)。我们要保证：\(val - cur > cur - left\) 恒成立。因此 \(val > 2 *cur\)，由于 \(cur\) 最大为 \(10^9\)，因此 \(val = 2 * 10^9\)
代码1
两边扫描优化未优化空间版本
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 2e5 + 10, INF = 2e9;
int n, m, a[N];
bool st[N];
PII l[N], r[N];
int ans[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < n + m; i ++ ) cin >> a[i];
for(int i = 0; i < n + m; i ++ ) cin >> st[i];
// 从左往右扫描
int left_max = INF, left_pos = -1; // 哨兵
for(int i = 0; i < n + m; i ++ )
{
if(st[i] == 0)
{
if(left_max == INF) l[i] = {INF, m + n + 1}; // 避免爆减法爆int
else l[i] = {a[i] - left_max, left_pos};
}
else left_max = a[i], left_pos = i;
}
// 从右向左扫描
int right_min = INF, right_pos = -1;
for(int i = n + m - 1; i >= 0; i -- )
{
if(st[i] == 0)
{
if(right_min == INF) r[i] = {INF, m + n + 1};
else r[i] = {right_min - a[i], right_pos};
}
else right_min = a[i], right_pos = i;
}
for(int i = 0; i < n + m; i ++ )
{
if(st[i] == 0)
{
if(l[i].first <= r[i].first) ans[l[i].second] ++ ;
else ans[r[i].second] ++ ;
}
}
for(int i = 0; i < n + m; i ++ )
if(st[i])
cout << ans[i] << ' ';
cout << endl;
return 0;
}
代码2
两边扫描优化空间版
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2e5 + 10, INF = 2e9;
int n, m, a[N];
bool st[N];
int l[N], r[N];
int ans[N / 2];
int main()
{
cin >> n >> m;
for(int i = 0; i < n + m; i ++ ) cin >> a[i];
for(int i = 0; i < n + m; i ++ ) cin >> st[i];
// 从左往右扫描
int left_max = INF; // 哨兵
for(int i = 0; i < n + m; i ++ )
{
if(st[i] == 0)
{
if(left_max == INF) l[i] = INF; // 避免爆减法爆int
else l[i] = a[i] - left_max;
}
else left_max = a[i];
}
// 从右向左扫描
int right_min = INF;
for(int i = n + m - 1; i >= 0; i -- )
{
if(st[i] == 0)
{
if(right_min == INF) r[i] = INF;
else r[i] = right_min - a[i];
}
else right_min = a[i];
}
int idx = 0;
for(int i = 0; i < n + m; i ++ )
{
if(st[i] == 0)
{
if(l[i] <= r[i]) ans[idx] ++ ;
else ans[idx + 1] ++ ;
}
else idx ++ ;
}
for(int i = 1; i <= m; i ++ ) cout << ans[i] << ' ';
cout << endl;
return 0;
}
代码3
二分
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010, INF = 1e9 + 1e9;
int n, m, ans[N];
int c[N << 1], a[N], b[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < n + m; i ++ ) cin >> c[i];
for(int k = 0, i = 0, j = 0; k < n + m; k ++ )
{
bool t; cin >> t;
if(t) b[ ++ j ] = c[k]; // 这里是先++是为了空位0放置哨兵
else a[i ++ ] = c[k];
}
/* 哨兵
因为存在一个居民左侧没有垃圾桶或者右侧没有垃圾桶的情况，所以在二分的时候我们要设置一个边界
但是为啥设置为 2e9 呢？
*/
b[0] = -INF, b[m + 1] = INF;
for(int i = 0; i < n; i ++ )
{
int l = 0, r = m + 1, pos = a[i];
while(l < r)
{
int mid = l + r >> 1;
if(b[mid] >= pos) r = mid;
else l = mid + 1;
}
// 由于 r/l 是 i 右侧最近的，那么 r-1 的位置必然是 i 左侧最近的
if((LL)pos - b[r - 1]<= (LL)b[r] - pos) // 这里要留意是否会溢出
ans[r - 1] ++ ;
else ans[r] ++ ;
}
for(int i = 1; i <= m; i ++ ) cout << ans[i] << ' ';
cout << endl;
return 0;
}
代码4
双指针