| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1330621 | bradley0927 | Room Temperature (JOI24_ho_t1) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
using namespace std;
int n, t;
vector<int> v;
int max_discomfort(int x) {
int max_d = 0;
for (int i = 0; i < v.size(); i++) {
int k = max(0, (v[i] - x)/t);//optimal jacket count
int temp = v[i] - k*t;
max_d = max(max_d, abs(x - temp));
}
return max_d;
}
int main() {
//ans = sum of modulo?
int mx = 0, mn = INT_MAX;
cin >> n >> t;
v.resize(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
mx = max(mx, v[i]);
mn = min(mn, v[i]);
}
//ternery search
int l = mn, r = mx;
while (r - l > 2) {
int m1 = l + (r - l)/3;
int m2 = r - (r - l)/3;
if (max_discomfort(m1) < max_discomfort(m2)) r = m2;
else l = m1;
}
int ans = INT_MAX;
for (int i = l; i <= r; i++) ans = min(ans, max_discomfort(i));
cout << ans << endl;
}
