/**//* 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
搜索
最新评论
|
|