22981(휴먼 파이프라인) - 해결

휴먼 파이프라인

 

문제

오늘은 중요한 날이다. SUAPC가 있는 날이기 때문이다.

이렇게 중요한 날이지만 안타깝게도 일을 해야 한다. 오늘 해야 할 일은 상자 K$K$개를 적절한 곳으로 옮겨야 하는 일이다.

상자 K$K$개는 너무 많아서 아무래도 혼자서 전부 나를 수는 없기 때문에, N$N$명의 SUAPC 참가자들이 상자를 나르기 위해 모여 있다. N$N$명 모두가 일을 최대한 빠르게 마치고 SUAPC에 참가하고 싶어한다.

참가자들은 두 팀으로 나눠져서 작업을 진행하기로 했다. 두 팀이 같은 수의 상자를 옮길 필요는 없다. 두 팀 모두 적어도 한 명은 포함되어야 한다. 각 사람의 분당 작업 속도는 vi$v_i$며 팀의 작업 속도는

 ($($해당 팀에 속한 사람들의 작업 속도 중 가장 느린 작업 속도)×($)\times($팀에 속한 사람의 수)$)$ 

이다. 상자 K$K$개를 옮기는 팀의 분당 작업 속도가 v$v$일 때, 팀이 작업을 마치는 데에는 ⌈Kv⌉$\left\lceil \frac{K}{v} \right\rceil$분이 걸린다.

모두가 행복하게 SUAPC에 참가할 수 있게, 모든 상자를 최대한 빠르게 옮길 수 있도록 N$N$명을 적절히 두 팀으로 나누어 두 팀이 동시에 상자를 옮기기 시작했을 때 제일 빨리 끝나는 경우의 시간을 구하자.

 

입력

다음과 같이 입력이 주어진다.

 N$N$  K$K$ 
v1$v_1$ v2$v_2$ ⋯$\cdots$ vN$v_N$ 

•  N$N$은 모인 사람의 수다. (2≤N≤200000$2 \le N \le 200\,000$)
•  K$K$는 옮겨야 하는 상자의 개수이다. (1≤K≤1018$1 \le K \le 10^{18}$)
•  vi$v_i$는 i$i$번째 사람의 분당 작업 속도이며, 1분에 상자 vi$v_i$개를 옮길 수 있다는 뜻이다. (1≤vi≤109$1 \le v_i \le 10^9$)
• 입력으로 주어지는 모든 수는 정수다.

출력

모든 상자를 최대한 빠르게 옮기는 경우의 작업 시간을 분 단위로 출력한다.

---

2팀으로 나누고 가장 작은 값을 기준으로 하기 때문에 정렬을 하고 인덱스를 기준으로 팀을 나눈다.

정렬을 하면 첫번째 팀은 가장 앞의 값이 가장 작은 값이고 2번째 팀은 인덱스의 값이 가장 작은 값이다.

그리고 인덱스까지가 첫번째 팀의 수이고 전체에서 인덱스를 빼면 2번째 팀의 수.

import sys
input = sys.stdin.readline

N, K = map(int,input().split())
people = list(map(int,input().split()))
# 정렬
people.sort()

# 맥스 v 저장
max_v = 0
# 2번째 부터 시작
for i in range(1,N):
    # 인덱스를 기준으로 나누기
    # 한칸씩가면서 정렬이 되어있기 때문에 가장 앞과 인덱스의 값이 가장 작은 값
    # 그래서 v를 첫번째 값에 인덱스에 인덱스값에 나머지 사람
    v = people[0] * i + people[i] * (N-i)
    
    # 맥스 저장
    if max_v < v:
        max_v = v

# 나머지가 있으면 1 더하기
if K % max_v:
    print(K//max_v + 1)
else:
    print(K//max_v)