Hướng dẫn giải của Tổng M
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
Dãy đã sắp xếp tăng dần. Cần tìm các cặp chỉ số ~i < j~ với ~a_i + a_j = M~. Đáp án in theo từng i: với mỗi ~i~, nếu có ~j > i~ thỏa mãn thì in một dòng "i j" với ~j~ lớn nhất (dãy có thể có các giá trị bằng nhau, nên một ~i~ có thể ghép được với nhiều ~j~, nhưng test chỉ in ~j~ lớn nhất). Nếu không có cặp nào thì in -1. Quy tắc này được xác nhận trên bộ test chấm, nhưng đề bài mô tả chưa đủ rõ về trường hợp có nhiều cặp.
Sub 1: Vét cạn — ~O(n^2)~, dùng khi ~n \le 1000~
Với mỗi ~i~, quét ~j~ từ ~n~ xuống đến ~i + 1~ và in cặp đầu tiên tìm được. Nếu chỉ nộp sub này: đúng 12/20 test.
Sub 2: Tìm nhị phân — ~O(n \log n)~
Với mỗi ~i~, cần giá trị ~M - a_i~ nằm trong đoạn ~(i, n]~. Dùng upper_bound để lấy vị trí đầu tiên có giá trị lớn hơn ~M - a_i~, lùi một bước để được ~j~ lớn nhất có ~a_j \le M - a_i~, rồi kiểm tra ~a_j~ đúng bằng ~M - a_i~. Bẫy: ~M~ và ~a_i~ có thể lên tới ~10^9~, tổng có thể vượt ~2 \cdot 10^9~, nên dùng long long. Sub 2 đúng 20/20 test.
Chương trình hoàn chỉnh
Hàm main đọc ~N, M~ và dãy. Nếu ~N \le 1000~ thì gọi sub 1, còn lại gọi sub 2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long M;
long long a[1000005]; // dãy đã sắp xếp tăng dần, a[1..n]
bool found = false; // đã in cặp nào chưa
// Quy tắc in (theo ví dụ kiểm tra): với mỗi i từ 1 đến n, nếu tồn tại j > i có a_i + a_j = M
// thì in một dòng "i j" với j là chỉ số LỚN NHẤT thỏa mãn.
// Sub 1: vét cạn O(n^2) — với mỗi i, quét j từ n xuống, gặp cặp đúng đầu tiên thì in. Dùng khi n <= 1000
void sub1() {
for (int i = 1; i <= n; i++)
for (int j = n; j > i; j--)
if (a[i] + a[j] == M) {
cout << i << " " << j << "\n";
found = true;
break;
}
if (!found) cout << -1 << "\n";
}
// Sub 2: với mỗi i, tìm j lớn nhất sao cho a[j] <= M - a[i] bằng binary search, O(n log n)
void sub2() {
for (int i = 1; i <= n; i++) {
long long need = M - a[i];
// vị trí đầu tiên có giá trị > need trong đoạn (i, n]; lùi 1 bước để được j lớn nhất có a[j] <= need
int pos = upper_bound(a + i + 1, a + n + 1, need) - a;
int j = pos - 1;
if (j > i && a[j] == need) {
cout << i << " " << j << "\n";
found = true;
}
}
if (!found) cout << -1 << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> M;
for (int i = 1; i <= n; i++) cin >> a[i];
if (n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận