 /**//*
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
搜索
最新評論

|
|