m개의 원소를 조건에 맞게 n개의 원소에 배치하는 방법

C - Kaiten Sushi

C - Kaiten Sushi

 

 

i번째 사람의 미각 점수는 A[i]로 주어지고, j번째 초밥은 맛 점수가 B[j]로 주어진다.

 

j = 1,2,..,m번 초밥이 1번부터 n번 사람에게 순서대로 주어지는데 A[i] <= B[j]인 모든 B[j]를 먹는다.

 

각각의 초밥이 어떤 사람에게 먹어지는지 결정한다.

 

n,m <= 200000

 

예를 들어 A = [3,8,2], B = [5,2,1]인데 B[0] = 5가 1번 사람에게 주어질때, A[0] <= B[0]이므로 B[0]를 먹는다.

 

B[1] = 2가 1번 사람에게 주어지는데, A[0] > B[1]이므로, 1번 사람은 B[1]은 먹지 않는다.

 

마찬가지로 A[1] = 8인데, A[1] > B[1]이므로 2번 사람은 B[1]을 먹지 않는다.

 

A[2] = 2인데, B[1] = 2이므로, A[2] >= B[1]이라서, 3번 사람은 B[1]을 먹는다.

 

B[2] = 1인데, A[0], A[1], A[2] > B[2]이므로 모든 사람은 B[2]를 먹지 않는다

 

그래서, 1,3,-1을 출력

 

사실 쉽게 생각하면 O(NM)으로

 

n,m = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))

for i in range(m):
    
    answer = -1
    
    for j in range(n):
        
        if A[j] <= B[i]:
            
            answer = j+1
            break
    
    print(answer)

 

 

n,m <= 20만이라 시간초과날게 뻔하다

 

여기서 생각해보면 i번째 사람의 미각 점수가 A[i]일때, 초밥의 맛 점수가 r이면, A[i] <= r인 경우,

 

i번째 사람은 무조건 A[i], A[i]+1, A[i]+2,...,r 초밥을 모두 먹을 수 있다.

 

그러면 i+1번째 사람은 A[i]-1, A[i]-2, ..., 초밥을 먹게 된다.

 

 

처음에 r = max(B)라 하고, i = 0,1,2,..,n-1에 대하여... 

 

A[i] <= r이면, A[i],A[i]+1,A[i]+2,...,r 초밥은 모두 i+1번 사람이 먹을 수 있다고 표시한다.

 

즉, j = A[i],A[i]+1,..,r에 대하여 id[j] = i+1이라고 표시해둔다.

 

그리고 r = A[i]-1이라고 갱신

 

모든 과정이 끝나면 i = 0,1,2,..,m-1에 대하여 B[i] 초밥은 누가 먹었는지 id[B[i]]로 찾을 수 있다.

 

n,m = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))

r = max(B)

id = [-1]*(r+1)

for i in range(n):
    
    if A[i] <= r:
        
        for j in range(A[i],r+1):
            
            id[j] = i+1

        r = A[i] - 1

for i in range(m):
    
    print(id[B[i]])

 

 

혹은 A,B를 합친 다음 정렬하는데 예를 들어서

 

A = [3,8,2]

B = [5,2,1]

 

C = [(3,A,0), (8,A,1), (2,A,2), (5,B,0), (2,B,1), (1,B,2)]

 

이걸 정렬하면

 

C = [(1,B,2), (2,A,2), (2,B,1), (3,A,0), (5,B,0), (8,A,1)]

 

왼쪽부터 검색하는데 (1,B,2)를 만나는데 A를 만난 것이 없으므로 B[2] = 1은 먹는 사람이 없다

 

(2,B,1)을 만날때, (2,A,2)를 만났으므로, B[1]은 3번 사람이 먹었다

 

(5,B,0)을 만났을때 (3,A,0)을 만났으므로 B[0]는 1번 사람이 먹었다.

 

n,m = map(int,input().split())

A = list(map(int,input().split()))
B = list(map(int,input().split()))

C = []

for i in range(n):
    
    C.append((A[i],0,i))

for i in range(m):
    
    C.append((B[i],1,i))

C.sort()
    
answer = [0]*m

INF = 100000000000000000000000000000000
x = INF

for i in range(len(C)):
    
    a,j,k = C[i]

    if j == 1:
        
        if x == INF:

            answer[k] = -1
        
        else:
            
            answer[k] = x

    
    else:
        
        if x > k+1:

            x = k+1
        
print('\n'.join(map(str,answer)))