Hướng dẫn giải của [2627 KS3_DE2] Câu 1: Tiền điện bậc thang
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
Mỗi hộ có m bậc thang với các mốc c1 < ... < c{m-1} và giá p1 ≤ ... ≤ pm. Cho số tiền T, tìm số kWh nhiều nhất mà hộ có thể dùng sao cho tiền điện không vượt T.
Sub 1: Tìm nhị phân trên số kWh — ~O(m · log(10^18) · t)~
Tiền điện là hàm tăng theo số kWh x, nên tìm x lớn nhất có cost(x) ≤ T bằng tìm nhị phân trên đoạn [0, 2·10^18]. Với mỗi x, tính cost(x) bằng cách cộng tiền từng bậc. Dùng __int128 để tránh tràn số khi nhân.
Kết quả chấm: 20/20 (SUB ok 20/20, TLE 0, WA 0)
#include <bits/stdc++.h>
using namespace std;
typedef __int128 lll;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int t;
cin >> t;
while (t--) {
int m;
long long T;
cin >> m >> T;
vector<long long> c(m + 1, 0), p(m + 1, 0);
for (int i = 1; i < m; i++) cin >> c[i];
for (int i = 1; i <= m; i++) cin >> p[i];
// Ham tien dien khi dung x kWh (cong don cac bac)
auto cost = [&](long long x) -> lll {
lll s = 0;
for (int i = 1; i <= m; i++) {
long long lo = c[i - 1];
long long hi = (i < m) ? c[i] : LLONG_MAX;
long long used = min(x, hi) - lo;
if (used < 0) used = 0;
s += (lll)used * p[i];
}
return s;
};
// Tim tim x lon nhat co cost(x) <= T bang chat nhi phan
long long lo = 0, hi = 2000000000000000000LL; // cost(lo) <= T, cost(hi) > T
while (hi - lo > 1) {
long long mid = lo + (hi - lo) / 2;
if (cost(mid) <= (lll)T) lo = mid;
else hi = mid;
}
cout << lo << "\n";
}
return 0;
}
Sub 2: Tiêu thụ theo bậc — ~O(m · t)~
Vì giá các bậc tăng dần, nên dùng tiền từ bậc 1 trước: nếu đủ tiền để mua trọn bậc i thì trừ tiền và cộng số kWh của bậc đó; nếu không đủ thì mua thêm T/pi kWh rồi dừng. Bậc cuối không giới hạn nên mua thêm T/pm kWh. Dùng long long vì len·p có thể đến 10^18.
Kết quả chấm: 20/20 (PASS 20/20)
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
if (fopen("CAU1.INP", "r")) { freopen("CAU1.INP", "r", stdin); freopen("CAU1.OUT", "w", stdout); }
int t;
cin >> t;
while (t--) {
int m;
long long T;
cin >> m >> T;
vector<long long> c(m + 1, 0), p(m + 1, 0); // c[0] = 0
for (int i = 1; i < m; i++) cin >> c[i];
for (int i = 1; i <= m; i++) cin >> p[i];
long long kwh = 0, tien = T;
bool het = false;
// Bac i co len = c[i] - c[i-1] kWh. Gia bac tang dan nen tieu thu tu bac 1 den bac m.
for (int i = 1; i < m && !het; i++) {
long long len = c[i] - c[i - 1];
long long cost = len * p[i];
if (tien >= cost) { tien -= cost; kwh += len; }
else { kwh += tien / p[i]; het = true; } // het tien trong bac nay
}
// Bac cuoi (bac m) khong gioi han so kWh
if (!het) kwh += tien / p[m];
cout << kwh << "\n";
}
return 0;
}
Bình luận