Hướng dẫn giải của Bài toán tìm số (đề Trà Vinh 2021)
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
Tìm đoạn liên tiếp có tổng lớn nhất.
Sub 1: Vét cạn, ~O(n^2)~ (n ≤ 200)
Thử mọi cặp (i, j) dùng tổng tiền tố. Đúng 25/25 test.
Sub 2: Tiền tố nhỏ nhất, ~O(n)~
Với mỗi đầu cuối j, tổng lớn nhất = P[j] - min P[i] với i < j. Đúng 25/25 test.
Chương trình hoàn chỉnh
main: n ≤ 200 gọi sub1, còn lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n;
vector<long long> a, P; // P[k] = a[1] + ... + a[k], P[0] = 0
long long best;
int bi, bj; // doan tim duoc la a[bi+1..bj] (chi so tinh tu 0 trong P)
// Quy uoc chon doan khi co nhieu doan cung tong lon nhat: uu tien doan ket thuc som nhat,
// roi bat dau som nhat.
// Sub 1: vet can. Thu moi cap (i, j) voi 0 <= i < j <= n, tinh tong a[i+1..j] bang P[j] - P[i].
void sub1() {
best = LLONG_MIN;
for (int j = 1; j <= n; j++)
for (int i = 0; i < j; i++) {
long long sum = P[j] - P[i];
if (sum > best) {
best = sum;
bi = i;
bj = j;
}
}
}
// Sub 2: voi moi dau ket thuc j, tong lon nhat ket thuc tai j = P[j] - min(P[i]) voi i < j.
// Giu lai min P[i] (va chi so nho nhat do) khi duyet j tang dan.
void sub2() {
best = LLONG_MIN;
long long mn = P[0];
int mnIdx = 0;
for (int j = 1; j <= n; j++) {
long long sum = P[j] - mn;
if (sum > best) {
best = sum;
bi = mnIdx;
bj = j;
}
if (P[j] < mn) {
mn = P[j];
mnIdx = j;
}
}
}
int main() {
freopen("tong.inp", "r", stdin);
freopen("tong.out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
a.assign(n + 1, 0);
P.assign(n + 1, 0);
for (int i = 1; i <= n; i++) {
cin >> a[i];
P[i] = P[i - 1] + a[i];
}
if (n <= 200) sub1();
else sub2();
cout << best << "\n" << bi + 1 << "\n" << bj - bi << "\n";
return 0;
}
Bình luận