Hướng dẫn giải của [200 đề thầy Đức] Bài 157: Vị trí cân bằng
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 tìm vị trí cân bằng đầu tiên: tổng các phần tử bên trái bằng tổng các phần tử bên phải. Nếu không có thì in -1. Vị trí đánh số từ 1.
Sub 1: Tính lại tổng trái và phải cho từng vị trí — ~O(N^2)~
Với mỗi vị trí ~i~, cộng lại tổng bên trái và tổng bên phải rồi so sánh. Đạt 13/21 test, 8 test lớn quá giờ vì N lên tới 10^5.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
// Vét cạn O(N^2): với mỗi vị trí i, tính lại tổng bên trái và bên phải
int ans = -1;
for (int i = 0; i < n && ans == -1; i++) {
long long left = 0, right = 0;
for (int j = 0; j < i; j++) left += a[j];
for (int j = i + 1; j < n; j++) right += a[j];
if (left == right) ans = i + 1; // vị trí đánh số từ 1
}
cout << ans << "\n";
}
return 0;
}
Sub 2: Dùng tổng toàn bộ và tổng cộng dồn — ~O(N)~
Gọi ~total~ là tổng cả dãy. Với vị trí ~i~, tổng trái là ~left~ và tổng phải là ~total - left - a[i]~. Cân bằng khi ~2 \cdot left + a[i] = total~. Tổng có thể lên tới 10^13 nên dùng long long. Đạt 21/21 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
vector<long long> a(n);
long long total = 0;
for (auto &x : a) {
cin >> x;
total += x;
}
// Với vị trí i: tổng trái = left, tổng phải = total - left - a[i].
// Cân bằng khi left = total - left - a[i], tức là 2*left + a[i] = total.
long long left = 0;
int ans = -1;
for (int i = 0; i < n; i++) {
if (2 * left + a[i] == total) {
ans = i + 1; // vị trí đánh số từ 1
break;
}
left += a[i];
}
cout << ans << "\n";
}
return 0;
}
Bình luận