Editorial for Nổ nữa nổ mãi 2
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Cách tiếp cận để giải quyết bài này là kết hợp quét từ trái sang phải với quét từ phải sang trái (có thể quét bằng tham lam hoặc QHĐ). Đầu tiên, ta chạy một thuật toán tham lam/DP từ trái sang phải để xác định cho mỗi quả bom cần phải nổ với sức mạnh tối thiểu là bao nhiêu để lan tỏa hết về phía trái. Sau đó, ta thực hiện điều tương tự từ phải sang trái, tính toán cho mỗi quả bom cần phải nổ với sức mạnh tối thiểu là bao nhiêu để lan tỏa hết về phía phải. Cuối cùng, bằng cách duyệt qua các quả bom, chúng ta có thể sử dụng hai con số này để xác định điểm tốt nhất nơi ta nên đặt vụ nổ ban đầu.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pi pair<ll, ll>
#define fi first
#define se second
int main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
// freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
int N; cin >> N;
vector<int> A(N);
for (int i = 0; i < N; i++) {
cin >> A[i];
A[i] *= 2;
}
sort(A.begin(), A.end());
A.resize(unique(A.begin(), A.end()) - A.begin());
vector<int> DP[2];
for (int it = 0; it < 2; it++) {
int lstj = 0;
DP[it].resize(N, INT_MAX);
DP[it][0] = -2;
for (int i = 1; i < N; i++) {
while (lstj + 1 < i && abs(A[i] - A[lstj + 1]) > DP[it][lstj + 1] + 2) {
lstj++;
}
DP[it][i] = min(abs(A[i] - A[lstj]), DP[it][lstj + 1] + 2);
}
reverse(A.begin(), A.end());
}
reverse(DP[1].begin(), DP[1].end());
int i = 0;
int j = N - 1;
int result = INT_MAX;
while (i < j) {
result = min(result, max((A[j] - A[i]) / 2, 2 + max(DP[0][i], DP[1][j])));
if (DP[0][i + 1] < DP[1][j - 1]) {
i++;
} else {
j--;
}
}
cout << result / 2 << '.' << (result % 2 ? 5 : 0) << '\n';
return 0;
}
Comments