 /**//*
n<=10^5只mice,m<=10^5個(gè)chese分別在兩條水平線上
每只老鼠會(huì)選擇離它最近的chese,然后同時(shí)出發(fā),若到達(dá)目標(biāo)處還有chese,就會(huì)吃(幾個(gè)同時(shí)到達(dá)的一起吃)
后來的就沒有了
若有多個(gè),會(huì)選擇使最后空肚子的mice數(shù)最少的那塊chese
問最后有多少只mice要空肚子
貪心
對(duì)每只老鼠,尋找跟它最近的1個(gè)或2個(gè)點(diǎn),設(shè)為left,right
如果left的chese還沒被吃或者之前老鼠到達(dá)它的時(shí)間跟當(dāng)前這只一樣的話,該老鼠不會(huì)餓肚子了
如果之前的老鼠達(dá)到它的時(shí)間比當(dāng)前這只長,而且當(dāng)前這只老鼠只有l(wèi)eft這個(gè)點(diǎn)最近,那很抱歉,之前那只老鼠沒得吃了,
給這只老鼠吃了
否則(即有兩個(gè)最近點(diǎn)),選擇右邊的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
搜索
最新評(píng)論

|
|