Hướng dẫn giải của [VTT Q4 Contest 02] Bài 1: Giá trị nhỏ nhất [MINSEG]
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
Cần kiểm tra dãy có không giảm hay không, và nếu có thì tìm hiệu dương nhỏ nhất giữa hai phần tử liền kề. Chỉ cần một lần duyệt các cặp liền kề.
Sub 1: Duyệt các cặp liền kề — ~O(n)~
Duyệt ~i = 1, \dots, n-1~, tính ~d = a_{i+1} - a_i~. Nếu ~d < 0~ thì dãy không tăng dần, in -1 ngay. Ngược lại, nếu ~d > 0~ thì cập nhật giá trị nhỏ nhất. Cuối cùng nếu chưa có hiệu dương nào (mọi phần tử bằng nhau, hoặc ~n = 1~) thì in 0, nếu có thì in hiệu nhỏ nhất. Bài này đơn giản, không có cách vét cạn hợp lý hơn nên chỉ có một sub. Chương trình đúng 10/10 test.
Chú ý: hiệu có thể lên tới ~2 \cdot 10^9~ nên phải dùng long long.
Chương trình hoàn chỉnh
main đọc dữ liệu rồi gọi sub1.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100005];
// Sub 1 (duy nhất): bài chỉ cần một lần duyệt, không có cách vét cạn nào hợp lý hơn.
// Duyệt các cặp liền kề: gặp hiệu âm thì in -1, ngược lại lấy hiệu dương nhỏ nhất.
void sub1() {
long long best = LLONG_MAX;
for (int i = 1; i < n; i++) {
long long d = a[i + 1] - a[i];
if (d < 0) { cout << -1; return; }
if (d > 0) best = min(best, d);
}
cout << (best == LLONG_MAX ? 0 : best);
}
int main() {
freopen("MINSEG.INP", "r", stdin);
freopen("MINSEG.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
sub1();
}
Bình luận