1. 문제 설명

• 문제 링크
  오늘은 중요한 날이다. SUAPC가 있는 날이기 때문이다. 이렇게 중요한 날이지만 안타깝게도 일을 해야 한다. 오늘 해야 할 일은 상자 $K$ 개를 적절한 곳으로 옮겨야 하는 일이다.

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

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

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

이다. 상자 $K$ 개를 옮기는 팀의 분당 작업 속도가 $v$ 일 때, 팀이 작업을 마치는 데에는

$\left\lceil \frac{K}{v} \right\rceil$ 분이 걸린다.

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

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

2. 풀이

• 정렬 후, 1칸씩 이동해가며 검사
• 항상 한 그룹은 모든 사람중 최하위 속도가 기본속도가 된다.
• => 정렬 후, 두 그룹의 총 속도를 계산해 봤을 때 최소값이 정답이 된다.

3. 코드

• c++

#include<iostream>
#include<algorithm>
#include<cmath>
#include<float.h>

using namespace std;

int N;
double K;
double human[200000];
int main(){
    cin >> N >> K;
    for(int i=0; i<N; i++){
        cin >> human[i];
    }
    
    sort(human, human + N);
    
    double minspeed = DBL_MAX;
    for(int i=1; i<=N-1; i++){
        double team1 = human[0] * (i);
        double team2 = human[i] * (N - i);
        long long left = (long long)K % ((long long)team1 + (long long)team2)
        if (left > 0){
            
        }
        double speed = K / (team1 + team2);
        if(minspeed > speed){
            minspeed = speed;
        }
    }
    long long answer = ceil(minspeed);
    cout << answer << endl;

    return 0;
}

• python

import math

N, K = map(int, input().split())
human = list(map(int, input().split()))

human = sorted(human)
minspeed = 1000000000000000005

for i in range(1, N):
    team1 = human[0] * i
    team2 = human[i] * (N-i)
    left = K % (team1 + team2)
    if left > 0:
        temp_speed =  K // (team1 + team2) + 1
    else:
        temp_speed = K // (team1 + team2)
    if minspeed > temp_speed:
        minspeed = temp_speed

print(minspeed)

4. 결과

알고리즘은 간단했다. 다만 실수를 계산하는 과정에서 처음에는 Ceil 함수를 사용해 올림을 했는데, 그 과정에서 문제가 생겼던것 같다. 그래서 Ceil을 간단하게 조건문으로 구현해주자, 통과할 수 있었다. 아마도 각 실수를 계산하는 과정에서 오차가 생기면서, 올림 조건에 부합되지 않는 경우가 발생하는 듯 하다.