Hướng dẫn giải của [Beginner Free Contest 09] ELECTION
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
n ứng cử viên có a_i phiếu, còn k người dân chưa bỏ phiếu. Kiểm tra xem có thể để tất cả ứng cử viên có cùng số phiếu sau khi k người bỏ phiếu hay không.
Sub 1: Thử từng số phiếu đích — ~O(n · k) mỗi bộ dữ liệu~
Gọi S là số phiếu chung cuối cùng. Với mỗi S từ max(ai) đến max(ai) + k, kiểm tra tổng (S - a_i) có bằng k không. Nếu có thì YES.
Kết quả chấm: 5/5 (SUB ok 5/5, TLE 0, WA 0)
#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;
long long k;
cin >> n >> k;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long mx = *max_element(a.begin(), a.end());
bool ok = false;
// Thu moi muc tieu so phieu S chung; can tong (S - a_i) = k
for (long long S = mx; S <= mx + k && !ok; S++) {
long long need = 0;
for (long long x : a) need += S - x;
if (need == k) ok = true;
}
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}
Sub 2: Công thức — ~O(n) mỗi bộ dữ liệu~
Khi tất cả có S phiếu thì n·S = (tổng ai) + k. Vậy cần (tổng ai + k) chia hết cho n, và S = (tổng ai + k)/n phải không nhỏ hơn max(ai) (vì phiếu chỉ được thêm, không được bớt).
Kết quả chấm: 5/5 (PASS 5/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;
long long k;
cin >> n >> k;
vector<long long> a(n);
long long tong = 0, mx = 0;
for (auto &x : a) { cin >> x; tong += x; mx = max(mx, x); }
// Sau bau, moi ung cu vien co S phieu: n*S = tong + k, va S >= max(a_i)
long long tongMoi = tong + k;
bool ok = (tongMoi % n == 0) && (tongMoi / n >= mx);
cout << (ok ? "YES" : "NO") << "\n";
}
return 0;
}
Bình luận