 /**//*
n<=10^5只mice,m<=10^5个chese分别在两条水平线上
每只老鼠会选择离它最近的chese,然后同时出发,若到达目标处还有chese,就会吃(几个同时到达的一起吃)
后来的就没有了
若有多个,会选择使最后空肚子的mice数最少的那块chese
问最后有多少只mice要空肚子
贪心
对每只老鼠,寻找跟它最近的1个或2个点,设为left,right
如果left的chese还没被吃或者之前老鼠到达它的时间跟当前这只一样的话,该老鼠不会饿肚子了
如果之前的老鼠达到它的时间比当前这只长,而且当前这只老鼠只有left这个点最近,那很抱歉,之前那只老鼠没得吃了,
给这只老鼠吃了
否则(即有两个最近点),选择右边的chese
(贪心选左边的,如果左边被人占了,看能不能吃右边的,不能的话,只好跟左边的竞争了,看谁快)

O(N+M)

3 1 1 0 --> 2
1 4 5
3

3 3 1 0 --> 0
-6 -4 -1
-6 -2 0
*/
#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>
#include<stack>
#include<queue>
#include<cmath>
#include<string>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<set>
#include<list>
#include<numeric>
#include<cassert>
#include<ctime>
#include<bitset>

using namespace std;

const int INF =0x3f3f3f3f;
const int MAXN = 100086;

int mice[MAXN], arr[MAXN], chese[MAXN];

int main()
  {
#ifndef ONLINE_JUDGE
freopen("in","r",stdin);
freopen("out","w",stdout);
#endif

 for (int n, m; ~scanf("%d%d%*d%*d", &n, &m); ) {
 for (int i = 0; i < n; i++) {
scanf("%d", &mice[i]);
}
 for (int i = 0; i < m; i ++) {
scanf("%d", &chese[i]);
}
fill(arr, arr+m, INF);
int ans = 0, now = 0;
 for (int i = 0; i < n ; i ++) {
 while(now + 1 < m && abs(mice[i]-chese[now+1]) < abs(mice[i]-chese[now])) {
now++;
}
int left = now , right = now+1 < m
&& abs(mice[i]-chese[now+1]) == abs(mice[i]-chese[now]) ? now+1 : now;
int dist = abs(mice[i] - chese[left]);
 if(arr[left] == INF) {
ans ++;
arr[left] = dist;
 } else if (arr[left] == dist) {
ans ++;
 } else if(arr[left] > dist && left == right) {//需要left = right
arr[left] = dist;
 } else if(left != right) {
arr[right] = dist;
ans++;
}
}
printf("%d\n", n - ans);
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|