D1. Chopping Carrots (Easy Version) | Round #809 Div.2

https://codeforces.com/contest/1706/problem/D1
시간 4초, 메모리 64MB

input :

• t (1 ≤ t ≤ 100)
• n k (1 ≤ n, k ≤ 3000)
• a1 a2 ... ai (1 ≤ a1 ≤ a2 ≤ an ≤ 109)

output :

• print a single integer — the minimum possible cost of an array p

조건 :

• 

---

idea

a1를 기준으로 잡고 이분탐색을 수행?
기본적으로 ai / a1으로 나누려고 하였다.
그러나 기준을 어떻게 잡아야 하는지가 문제임.

해설

1. 설정할 수 있는 값을 찾자(최소값의 범위는 지정이 가능하다)
2. 수의 범위도 적고 시간 제한도 크다. (충분히 완전탐색이 될 것)

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    n, k = map(int, sys.stdin.readline().split())
    data = list(map(int, sys.stdin.readline().split()))

    ans = float("inf")
    for min_value in range(1, data[0] + 1):
        max_value = -float("inf")

        for i in range(len(data)):
            pi = min(k, data[i] // min_value)
            max_value = max(max_value, data[i] // pi)

        ans = min(ans, max_value - min_value)

    print(ans)