Hướng dẫn giải của Cắt dây điện (đề HSG 9 Phú Thọ 2024-2025)
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ắt mọi cuộn dài hơn $h$ xuống $h$, phần thừa là $W(h) = \sum{ai > h} (a_i - h)$. $W(h)$ giảm khi $h$ tăng. Cần $W(h) \ge m$ và muốn dư ít nhất thì chọn $h$ lớn nhất thỏa điều kiện đó. Nếu $W(1) < m$ thì in $-1$.
Sub 1: Vét cạn — ~O(n \cdot \max a)~, dùng khi ~a_i \le 100~
Thử $h$ từ $\max a$ xuống $1$, tính $W(h)$ bằng vòng lặp qua $n$ cuộn, gặp $h$ đầu tiên có $W(h) \ge m$ thì in.
Nếu chỉ nộp sub này: đúng 8/20 test (12 test có $a_i$ lớn bị quá giờ).
Sub 2: Tìm kiếm nhị phân trên $h$ — ~O(n \log \max a)~
Vì $W(h)$ giảm đơn điệu nên dùng nhị phân để tìm $h$ lớn nhất với $W(h) \ge m$ trong đoạn $[1, \max a]$. Dùng long long vì $W(h)$ có thể lên tới $10^{15}$.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc dữ liệu, nếu $\max a \le 100$ 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; // can thu duoc it nhat m met phan thua
vector<long long> a; // chieu dai cac cuon day
long long maxA = 0;
// W(h) = tong phan thua khi cat moi cuon dai hon h xuong con h
long long waste(long long h) {
long long s = 0;
for (int i = 0; i < n; i++)
if (a[i] > h) s += a[i] - h;
return s;
}
// Sub 1: vet can, dung khi a_i <= 100 (maxA nho nen thu het h tu lon xuong nho)
void sub1() {
for (long long h = maxA; h >= 1; h--)
if (waste(h) >= m) { // h lon nhat ma W(h) >= m la dap an
cout << h << "\n";
return;
}
cout << -1 << "\n";
}
// Sub 2: tim kiem nhi phan. W(h) giam khi h tang, nen tim h lon nhat co W(h) >= m.
void sub2() {
if (waste(1) < m) { // ca khi cat xuong 1 met van khong du
cout << -1 << "\n";
return;
}
long long lo = 1, hi = maxA;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
if (waste(mid) >= m) lo = mid;
else hi = mid - 1;
}
cout << lo << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
a.resize(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
maxA = max(maxA, a[i]);
}
if (maxA <= 100) sub1(); // du lieu nho
else sub2();
return 0;
}
Bình luận