Hướng dẫn giải của DÃY SỐ
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
Mỗi thao tác cộng $1$ vào một phần tử. Muốn phần tử nhỏ nhất đạt giá trị $x$ thì mọi phần tử nhỏ hơn $x$ phải được tăng lên $x$, tốn $\sum \max(0, x - a_i)$ thao tác. Đáp số là giá trị $x$ lớn nhất với chi phí không vượt quá $m$.
Sub 1: Mô phỏng tham lam — ~O(m \log n)~, dùng khi ~m \le 10^5~
Mỗi lần lấy phần tử nhỏ nhất (hàng đợi ưu tiên) và cộng thêm $1$, lặp $m$ lần. Đáp số là phần tử nhỏ nhất cuối cùng.
Nếu chỉ nộp sub này: đúng 14/20 test (6 test có $m$ lớn quá giờ).
Sub 2: Tìm kiếm nhị phân trên giá trị — ~O(n \log m)~
Nếu đạt được $x$ thì mọi giá trị nhỏ hơn $x$ cũng đạt được, nên nhị phân trên $x$ trong đoạn $[\min a, \min a + m]$. Với mỗi $x$ tính chi phí $\sum \max(0, x - a_i)$ và so với $m$. Bẫy: chi phí có thể lên tới khoảng $4 \cdot 10^{14}$ nên dùng long long.
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 từ file CAU3.INP, ghi ra CAU3.OUT. Nếu $m \le 10^5$ 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;
vector<long long> a;
// Sub 1: mo phong tham lam, O(m log n), dung khi m <= 100000.
// Moi thao tac cong 1 vao phan tu nho nhat hien tai.
void sub1() {
priority_queue<long long, vector<long long>, greater<long long>> pq(a.begin(), a.end());
for (long long t = 0; t < m; t++) {
long long x = pq.top();
pq.pop();
pq.push(x + 1);
}
cout << pq.top() << "\n";
}
// Chi phi de moi phan tu co gia tri it nhat x: tong (x - a_i) voi a_i < x
long long costTo(long long x) {
long long c = 0;
for (long long v : a)
if (v < x) c += x - v;
return c;
}
// Sub 2: tim kiem nhi phan tren gia tri nho nhat dat duoc, dung cho moi m.
// Neu dat duoc gia tri x thi moi gia tri nho hon x cung dat duoc, nen nhi phan.
void sub2() {
long long mn = *min_element(a.begin(), a.end());
long long lo = mn, hi = mn + m;
while (lo < hi) {
long long mid = (lo + hi + 1) / 2;
if (costTo(mid) <= m) lo = mid;
else hi = mid - 1;
}
cout << lo << "\n";
}
int main() {
freopen("CAU3.INP", "r", stdin);
freopen("CAU3.OUT", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
a.resize(n);
for (auto &x : a) cin >> x;
if (m <= 100000) sub1();
else sub2();
return 0;
}
Bình luận