Hướng dẫn giải của Dãy con liên tiếp nhỏ nhất
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
Xếp dãy thành vòng tròn, cần tìm tổng nhỏ nhất của một đoạn liên tiếp trên vòng tròn (đoạn có độ dài từ 1 đến ~n~, có thể đi qua điểm nối cuối–đầu).
Sub 1: Vét cạn — ~O(n^3)~, dùng khi ~n \le 30~
Thử mọi vị trí bắt đầu ~i~ và mọi độ dài ~len~, tính tổng bằng cách cộng lại từng phần tử theo vòng tròn (chỉ số lấy ~\bmod n~). Chạy riêng sub này: đúng 20/20 test.
Sub 2: Tổng tiền tố trên mảng nhân đôi — ~O(n^2)~
Ghép hai bản sao của dãy để mọi đoạn vòng tròn thành đoạn thẳng, rồi dùng tổng tiền tố để có tổng đoạn trong ~O(1)~. Bẫy: độ dài đoạn không được vượt ~n~. Chạy riêng sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Chương trình đọc ~n~ và dãy; nếu ~n \le 30~ gọi sub1, còn lại gọi sub2.
Số test: 20 (chương trình đầy đủ đúng 20/20).
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[105]; // a[0..n-1]
// Sub 1: vet can. Voi moi vi tri bat dau i va moi do dai len (1..n), cong lai len cac phan tu
// trong vong tron roi lay tong nho nhat. O(n^3). Dung khi n <= 30
void sub1() {
long long best = LLONG_MAX;
for (int i = 0; i < n; i++)
for (int len = 1; len <= n; len++) {
long long s = 0;
for (int k = 0; k < len; k++) s += a[(i + k) % n];
best = min(best, s);
}
cout << best << "\n";
}
// Sub 2: dung mang tong tien to tren day nhan doi (ghep 2 ban sao cua A) de tinh tong
// cua moi doan vong tron trong O(1): tong doan bat dau i, do dai len = pd[i+len] - pd[i]. O(n^2)
void sub2() {
vector<long long> pd(2 * n + 1, 0);
for (int i = 0; i < 2 * n; i++) pd[i + 1] = pd[i] + a[i % n];
long long best = LLONG_MAX;
for (int i = 0; i < n; i++)
for (int len = 1; len <= n; len++)
best = min(best, pd[i + len] - pd[i]);
cout << best << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
if (n <= 30) sub1();
else sub2();
return 0;
}
Bình luận