Cho mảng D kích thước N. Amal và N người khác. Chênh múi giờ giữa Amal và người i là D[i] giờ. Khoảng cách giữa 2 thành phố: min(d, 24-d). Xét mọi cặp trong N+1 người, tìm giá trị lớn nhất của khoảng cách nhỏ nhất s.
Ví dụ
Với D=[7,12,8], đầu ra 4.
Giải thuật
Sắp xếp D. Xây mảng t: thêm 0, rồi xen kẽ D[i] và 24-D[i] (chẵn/lẻ). Sắp xếp t. Kết quả là khoảng cách nhỏ nhất giữa 2 phần tử liên tiếp trong t đã sắp xếp.
Mã C++
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> D) {
int n = D.size();
sort(D.begin(), D.end());
vector<int> t; t.push_back(0);
for (int i = 0; i < n; i++) {
if (i % 2 == 0) t.push_back(D[i]);
else t.push_back(24 - D[i]);
}
sort(t.begin(), t.end());
int ans = 1e9;
for (int i = 1; i < t.size(); i++) ans = min(ans, t[i] - t[i-1]);
return ans;
}
int main() {
vector<int> D = { 7, 12, 8 };
cout << solve(D) << endl;
}
Đầu vào / Đầu ra
Input: { 7, 12, 8 }
Output: 4