Hướng dẫn giải của Cặp đôi hoàn hảo (phiên bản 1)
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: , , ,
Hiểu bài toán
Cho một mảng số nguyên A có n phần tử. Nhiệm vụ là tìm hai phần tử lân cận nhau trong mảng (bao gồm cả cặp phần tử đầu tiên và cuối cùng) sao cho tổng của chúng là lớn nhất. Nếu có nhiều cặp có cùng tổng lớn nhất, ta phải chọn cặp có chỉ số của phần tử đầu tiên lớn hơn. Trong trường hợp đặc biệt, nếu cặp (phần tử cuối, phần tử đầu) là một trong các cặp có tổng lớn nhất, ta phải ưu tiên in ra cặp này theo thứ tự (phần tử cuối, phần tử đầu).
Các cách tiếp cận
Cách Duyệt qua tất cả các cặp lân cận
#include <stdio.h>
#include <limits.h>
int main() {
int n;
scanf("%d", &n);
int a[n];
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
// Khởi tạo max_sum bằng INT_MIN để xử lý số âm
long long max_sum = LLONG_MIN;
int idx1 = -1, idx2 = -1;
// Duyệt các cặp lân cận thông thường (i và i+1)
for (int i = 0; i < n - 1; i++) {
long long current_sum = (long long)a[i] + a[i+1];
if (current_sum > max_sum) {
max_sum = current_sum;
idx1 = i;
idx2 = i+1;
} else if (current_sum == max_sum) {
// Nếu bằng nhau, chọn cặp có chỉ số đầu tiên lớn hơn
if (i > idx1) {
idx1 = i;
idx2 = i+1;
}
}
}
// Xử lý cặp đặc biệt (cuối và đầu)
long long wrap_sum = (long long)a[n-1] + a[0];
if (wrap_sum > max_sum) {
// Nếu cặp này lớn hơn tất cả, in ra theo quy tắc đặc biệt
printf("%d %d", a[n-1], a[0]);
} else if (wrap_sum == max_sum) {
// Nếu bằng nhau, quy tắc đề bài nói "Nếu phần tử cuối cùng và phần tử đầu tiên là cặp có tổng lớn nhất, in phần tử cuối cùng trước"
// Điều này cho thấy cặp này luôn được ưu tiên in ra nếu nó thuộc nhóm tối ưu.
printf("%d %d", a[n-1], a[0]);
} else {
// In cặp tìm được (đã xét điều kiện chỉ số lớn hơn khi duyệt)
printf("%d %d", a[idx1], a[idx2]);
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Approach này duyệt qua mảng một lần để tính toán. Ta cần lưu ý việc khởi tạo giá trị maxsum (nên dùng long long và giá trị nhỏ nhất) để đảm bảo so sánh đúng với các cặp có tổng âm. Với mỗi cặp lân cận (i, i+1), ta so sánh tổng của chúng với maxsum hiện tại. Nếu lớn hơn, cập nhật. Nếu bằng nhau, ta chỉ cập nhật nếu chỉ số i lớn hơn chỉ số hiện tại. Cuối cùng, ta xét riêng cặp (cuối, đầu) theo quy tắc đặc biệt của đề bài.
Cách Quy tắc tối ưu (Single Pass)
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
long long max_sum = LLONG_MIN;
int best_idx = -1;
bool is_wrap = false;
// Kiểm tra cặp wrap-around trước
long long wrap_sum = a[n-1] + a[0];
if (wrap_sum >= max_sum) {
max_sum = wrap_sum;
is_wrap = true;
}
// Kiểm tra các cặp lân cận
for (int i = 0; i < n - 1; i++) {
long long current_sum = a[i] + a[i+1];
if (current_sum > max_sum) {
max_sum = current_sum;
best_idx = i;
is_wrap = false;
} else if (current_sum == max_sum) {
// Nếu bằng nhau, ưu tiên cặp có chỉ số lớn hơn (trừ khi là wrap đã có quy tắc riêng)
// Tuy nhiên, nếu wrap bằng max_sum, ta đã set is_wrap=true ở trên.
// Logic ở đây: nếu current_sum == max_sum và không phải là wrap.
// Ta cần chọn chỉ số lớn hơn.
if (!is_wrap && i > best_idx) {
best_idx = i;
is_wrap = false;
}
}
}
if (is_wrap) {
cout << a[n-1] << " " << a[0];
} else {
cout << a[best_idx] << " " << a[best_idx+1];
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là cách tiếp cận trực quan nhất. Ta chia bài toán thành 2 phần: tìm max ở các cặp (i, i+1) và so sánh với cặp (n-1, 0).
Quy tắc logic:
- Khởi tạo max_sum = -Infinity.
- Duyệt i từ 0 đến n-2:
- Tính S = A[i] + A[i+1]
- Nếu S > maxsum: cập nhật maxsum, lưu index i.
- Nếu S == max_sum: chỉ cập nhật index nếu i > index cũ (để thỏa mãn điều kiện chỉ số lớn nhất).
- Xét S_wrap = A[n-1] + A[0]:
- Nếu Swrap > maxsum: in A[n-1] A[0] và kết thúc.
- Nếu Swrap == maxsum: theo điều kiện 'nếu phần tử cuối cùng và phần tử đầu tiên là cặp có tổng lớn nhất, in phần tử cuối cùng trước', ta in A[n-1] A[0].
- Ngược lại in cặp tại index đã lưu.
Lưu ý về dấu '=': Trong Solution 1 và 3, tác giả dùng dấu >= hoặc kiểm tra if (wrap > max). Để xử lý đúng điều kiện 'chỉ số lớn hơn' và 'ưu tiên wrap', ta cần logic chính xác: Wrap luôn ưu tiên nếu bằng nhau. Với cặp thường, nếu bằng nhau thì ưu tiên index lớn hơn.
Cách Mô phỏng trực tiếp theo Sample
#include <stdio.h>
int main() {
int n;
scanf("%d", &n);
int a[10005];
for(int i=0; i<n; i++) scanf("%d", &a[i]);
long long maxVal = -2000000000000000000LL; // -2e18
int resIdx = -1;
int isWrap = 0;
// Check wrap first to handle priority if equal
long long wrapSum = (long long)a[n-1] + a[0];
if (wrapSum >= maxVal) {
maxVal = wrapSum;
isWrap = 1;
}
for (int i = 0; i < n - 1; i++) {
long long sum = (long long)a[i] + a[i+1];
if (sum > maxVal) {
maxVal = sum;
resIdx = i;
isWrap = 0;
} else if (sum == maxVal) {
// Nếu tổng bằng maxVal hiện tại
// Nếu maxVal hiện tại là do Wrap tạo ra (isWrap=1), ta không thay đổi vì Wrap có độ ưu tiên cao hơn hoặc bằng theo cách giải thích của đề
// Tuy nhiên, nếu cùng là pair thường, chọn index lớn hơn
if (!isWrap) {
if (i > resIdx) {
resIdx = i;
isWrap = 0;
}
}
// Nếu là Wrap, ta giữ nguyên isWrap=1
}
}
if (isWrap) {
printf("%d %d", a[n-1], a[0]);
} else {
printf("%d %d", a[resIdx], a[resIdx+1]);
}
return 0;
}
- Time Complexity: O(n)
- Space Complexity: O(n)
Đây là cách tiếp cận cẩn thận để xử lý tất cả các edge cases về độ ưu tiên.
- Luôn kiểm tra cặp wrap-around (cuối, đầu) đầu tiên hoặc xem xét nó ngang bằng với max.
- Ta ghi nhận
isWrapnếu cặp này đạt max. - Khi duyệt các cặp lân cận:
- Nếu tổng lớn hơn max hiện tại: cập nhật, hủy bỏ trạng thái Wrap.
- Nếu tổng bằng max hiện tại:
- Nếu max hiện tại là Wrap: không làm gì cả (Wrap ưu tiên hơn).
- Nếu max hiện tại là pair thường: so sánh index, lấy index lớn hơn. Điều này đảm bảo:
- Wrap thắng nếu bằng nhau.
- Pair thường thắng nếu lớn hơn.
- Pair thường có index lớn hơn thắng nếu bằng nhau với pair thường khác.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n) | O(n) | Duyệt qua tất cả các cặp lân cận |
| 2 | O(n) | O(n) | Quy tắc tối ưu (Single Pass) |
| 3 | O(n) | O(n) | Mô phỏng trực tiếp theo Sample |
Bài học kinh nghiệm
- Bài toán có tính chất vòng tròn, cần xử lý riêng cặp phần tử đầu và cuối.
- Điều kiện 'chỉ số lớn hơn' chỉ áp dụng khi xét các cặp lân cận thông thường có cùng tổng.
- Độ ưu tiên của cặp (cuối, đầu) được thể hiện qua việc nếu tổng bằng nhau thì in cặp này.
Lỗi thường gặp
- Sai kiểu dữ liệu: Tổng của 2 số có giá trị lên tới 10^8 có thể lên tới 2 * 10^8, nằm trong giới hạn của int (nếu là 32-bit), nhưng để an toàn và tránh tràn số khi so sánh với các giá trị âm lớn, nên dùng kiểu long long.
- Lỗi logic so sánh điều kiện 'bằng nhau'. Ví dụ, nếu không xử lý đúng, ta có thể chọn một cặp lân cận có index lớn hơn nhưng tổng bằng nhau, trong khi cặp (cuối, đầu) cũng có tổng bằng nhau nhưng bị bỏ qua.
Bình luận
include <bits/stdc++.h>
using namespace std; long long n,a[10001]; long long ln=LLONG_MIN; long long mot,hai; int main() { cin>>n; for(long long i=0;i<n;i++){ cin>>a[i]; } for(long long i=0;i<n-1;i++){ if(a[i]+a[i+1]>ln){ ln=a[i]+a[i+1]; mot=a[i]; hai=a[i+1]; } } if(a[0]+a[n-1]>ln){ ln=a[0]+a[n-1]; mot=a[n-1]; hai=a[0]; } cout<<mot<<" "<<hai; }