Hướng dẫn giải của [Beginner Free Contest 08] MAXDIFF
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho dãy tăng a gồm n phần tử. Xóa một phần tử bất kỳ sao cho khoảng cách lớn nhất giữa hai phần tử liên tiếp của dãy còn lại là lớn nhất có thể.
Sub 1: Xóa thử từng phần tử — ~O(n^2)~
Với mỗi vị trí i, tạo lại dãy sau khi xóa a[i] rồi duyệt để tìm khoảng cách lớn nhất giữa các phần tử liên tiếp. Lấy max trong các kết quả. Đơn giản, chạy được vì n ≤ 1000.
Kết quả chấm: 10/10 (SUB ok 10/10, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long best = 0;
// Thu xoa tung phan tu, sau do tinh lai do dep cua day con lai (O(n^2))
for (int i = 0; i < n; i++) {
vector<long long> b;
for (int j = 0; j < n; j++) if (j != i) b.push_back(a[j]);
long long cur = 0;
for (size_t j = 1; j < b.size(); j++) cur = max(cur, b[j] - b[j - 1]);
best = max(best, cur);
}
cout << best << "\n";
return 0;
}
Sub 2: Tiền tố và hậu tố — ~O(n)~
Tính trước pre[i] là khoảng cách lớn nhất giữa các cặp liên tiếp nằm trong a[0..i], và suf[i] là khoảng cách lớn nhất trong a[i..n-1]. Khi xóa a[i], các cặp còn lại gồm: cặp trong đoạn trái (pre[i-1]), cặp trong đoạn phải (suf[i+1]) và cặp bắc qua vị trí i là a[i+1] - a[i-1]. Lấy max ba giá trị này rồi lấy max theo i.
Kết quả chấm: 10/10 (PASS 10/10)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// pre[i]: khoang cach lon nhat giua cac cap ke tiep chi nam trong a[0..i]
// suf[i]: khoang cach lon nhat giua cac cap ke tiep chi nam trong a[i..n-1]
vector<long long> pre(n, 0), suf(n, 0);
for (int i = 1; i < n; i++) pre[i] = max(pre[i - 1], a[i] - a[i - 1]);
for (int i = n - 2; i >= 0; i--) suf[i] = max(suf[i + 1], a[i + 1] - a[i]);
long long best = 0;
for (int i = 0; i < n; i++) {
// Xoa a[i]: cac cap con lai la cac cap trong doan trai, doan phai, va cap bac qua vi tri i
long long cur = 0;
if (i - 1 >= 0) cur = max(cur, pre[i - 1]);
if (i + 1 < n) cur = max(cur, suf[i + 1]);
if (i - 1 >= 0 && i + 1 < n) cur = max(cur, a[i + 1] - a[i - 1]);
best = max(best, cur);
}
cout << best << "\n";
return 0;
}
Bình luận