Codeforces Round 823 (Div. 2) - Meeting on the Line 링크
(2023.09.13 기준 Difficulty *1600)

문제

n명의 사람들이 일직선 상에 살고 있다. 모든 사람들이 한 곳에 모이려고 하는데, 이동 시간은 좌표 차이만큼 걸리고 옷 입는 시간은 n명의 사람들마다 각각 주어진다.

최소 시간이 걸리는 위치 출력

풀이

삼분 탐색

알고리즘

모든 사람들이 만나는 시간은 곧, 가장 오래 걸리는 사람의 시간이다.

사람들의 각 위치에서 떨어질수록 이동 시간은 당연히 더 길어진다. 그러므로, 사람들의 위치의 최솟값과 최댓값 사이에 만나는 장소가 정해져야 한다.

옷 입는 시간이 주어졌으므로, 아래로 볼록한 함수는 맞지만 어디가 극솟값인지는 모른다. 그러므로, 삼분 탐색을 이용하여 극솟값을 찾으면 된다. 그리고 그 극솟값에 대한 x(만나는 장소)를 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1e5;

int N, X[MAXN], T[MAXN];

double f(double x){ // 사람들의 위치 x로 모이기 위한 걸리는 시간 중 최댓값 반환
    double result = 0;
    for (int i = 0; i < N; i++) result = max(result, fabs(X[i] - x) + T[i]);
    return result;
}

void solve(){
    cin >> N;
    for (int i = 0; i < N; i++) cin >> X[i];
    for (int i = 0; i < N; i++) cin >> T[i];

    // 삼분 탐색
    double st = 0, en = 1e8; // 모든 위치는 [0, 100,000,000] 구간에 포함된다.
    while (en - st > 1e-7){
        double mid_1 = (st * 2 + en) / 3;
        double mid_2 = (st + en * 2) / 3;
        if (f(mid_1) < f(mid_2)) en = mid_2; // 아래로 볼록 함수이므로 극솟값을 찾아야 한다.
        else st = mid_1;
    }

    cout << st << '\n';
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cout << fixed << setprecision(7);

    int T; cin >> T;
    while (T--) solve();
}

• Python

import sys; input = sys.stdin.readline

def f(x): # 사람들의 위치 x로 모이기 위한 걸리는 시간 중 최댓값 반환
    return max(abs(X[i] - x) + T[i] for i in range(N))

def solve():
    global N; N = int(input())
    global X; X = list(map(int, input().split()))
    global T; T = list(map(int, input().split()))

    # 삼분 탐색
    st = 0; en = 1e8 # 모든 위치는 [0, 100,000,000] 구간에 포함된다.
    while en - st > 1e-7:
        mid_1 = (st * 2 + en) / 3
        mid_2 = (st + en * 2) / 3
        if f(mid_1) < f(mid_2): # 아래로 볼록 함수이므로 극솟값을 찾아야 한다.
            en = mid_2
        else:
            st = mid_1

    print(st)

for _ in range(int(input())):
    solve()