다다스의 라면 먹방

$K$가 주어졌을 때 총 시간을

$$f(K)=\sum_{i=1}^N \min(A_i,K)$$

라고 하자.

$K$가 증가하면 각 항 $\min(A_i,K)$는 감소하지 않으므로 $f(K)$도 감소하지 않는다. 따라서 $f(K)\ge L$을 처음 만족하는 $K$를 이분 탐색으로 찾을 수 있다.

탐색 구간의 오른쪽 끝은 $\max A_i$로 두면 충분하다. 문제에서 정답의 존재가 보장되므로, 이분 탐색으로 찾은 최소의 $K$에서는 반드시 $f(K)=L$이다.

각 $K$에 대해 $f(K)$는 수열을 한 번 순회하여 $O(N)$에 계산할 수 있다. $A_i\le10^{13}$이므로 이분 탐색 횟수는 약 $44$번 이하이다. 전체 시간 복잡도는 테스트 케이스 전체에 대해

$$O\left(\left(\sum N\right)\log 10^{13}\right)$$

이고, 추가 공간 복잡도는 한 테스트 케이스당 $O(N)$이다.

또한 $\sum A_i\le 2\cdot10^{18}$이므로 $f(K)$와 모든 관련 합은 signed 64-bit 정수인 long long 범위 안에 들어간다.

Solution written by GPT5.6