만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

뮤지컬 트리즈

면접 대비

시간 제한1초메모리 제한1024 MB

요약
직선 위에 있는 사람과 나무의 위치가 주어집니다. 각 사람은 가장 가까운 나무로 달려가고 한 나무는 한 사람만 얻습니다. 나무를 받지 못하는 사람의 수를 구합니다.
난이도

쉬움10점 중 3점

유형
그리디, 구현
정답자
아직 제출이 없습니다

문제

크리스마스 시즌을 맞아 JW의 1차원 가게에서 크리스마스 트리를 판매하고 있다. 그러나 트리를 원하는 사람은 재고 트리 수보다 훨씬 많다. 그래서 JW는 누가 어떤 트리를 가져갈지 정하는 방법으로 Musical Trees 게임을 고안했다.

Musical Trees는 뮤지컬 의자와 비슷하다. 트리들은 일직선 위에 놓여 있다. 음악이 멈추면 모든 사람은 가장 가까운 트리, 즉 거리가 가장 짧은 트리를 향해 달린다. 먼저 도착한 사람이 그 트리를 차지한다. 사람들은 게을러서 자신에게 가장 가까운 트리만 향해 달리므로, 같은 트리로 여러 사람이 달릴 수 있다. 어느 사람에게도 가장 가깝지 않은 트리는 아무도 차지하지 못할 수 있다. 뮤지컬 의자와 마찬가지로, 한 트리를 두 명 이상이 차지할 수는 없다.

음악이 방금 멈췄고 모두 가장 가까운 트리로 달리고 있다. 트리를 받지 못하는 사람의 수를 구하시오.

일부 사람은 부정을 시도할 수 있어서, 음악이 멈췄을 때 이미 트리와 같은 위치에 서 있을 수 있다. 한 사람에게 가장 가까운 트리가 여러 개라면, 그 사람은 항상 tit_i가 가장 작은 트리로 간다.

입력

첫째 줄에 사람 수 nn (1≤n≤1001\le n\le 100)과 트리 수 mm (1≤m≤1001 \le m \le 100)이 주어진다. 둘째 줄에는 음악이 멈췄을 때 모든 사람의 위치 p1,p2,…,pnp_1,p_2,\ldots,p_n (1≤pi≤1 0001 \le p_i \le 1\,000)이 주어진다. 셋째 줄에는 모든 트리의 위치 t1,t2,…,tmt_1,t_2,\ldots,t_m (1≤ti≤1 0001 \le t_i \le 1\,000)이 주어진다. 두 사람의 위치는 같지 않고, 두 트리의 위치도 같지 않다.

출력

트리를 받지 못하는 사람의 수를 출력한다.

예제3

  1. 예제 1

    입력
    2 3
    1 4
    2 4 5
    
    예상 출력
    0
    
  2. 예제 2

    입력
    3 2
    1 5 10
    4 6
    
    예상 출력
    1
    
  3. 예제 3

    입력
    2 3
    3 1
    2 5 4
    
    예상 출력
    1