Hướng dẫn giải của Dự án (KS3)
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
Tim von ban dau it nhat de thuc hien moi du an (tra ai truoc, nhan bi sau). Dung cong thuc nguoc need = max(ai, need + ai - b_i).
Sub 1: Thu moi thu tu, ~n \le 8~ ~O(n! \cdot n)~
Thu moi hoan vi cua cac du an. Chay rieng: dung 6/20 test.
Sub 2: Sap xep, ~n \le 10^5~ ~O(n \log n)~
Du an co loi (b >= a) lam truoc, sap theo a tang dan; du an co lo lam sau, sap theo b giam dan. Chay rieng: dung 20/20 test.
Chương trình hoàn chỉnh
Neu n <= 8 dung sub 1, nguoc lai dung sub 2.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
vector<ll> a, b;
// Von ban dau can thiet khi lam cac du an theo thu tu ord: duyet nguoc, need = max(a_i, need + a_i - b_i)
ll needFor(const vector<int>& ord) {
ll need = 0;
for (int k = (int)ord.size() - 1; k >= 0; k--) {
int i = ord[k];
need = max(a[i], need + a[i] - b[i]);
}
return need;
}
// Sub 1: vet can tat ca thu tu, dung khi n <= 8
void sub1() {
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
ll best = LLONG_MAX;
do {
best = min(best, needFor(ord));
} while (next_permutation(ord.begin(), ord.end()));
cout << best << "\n";
}
// Sub 2: tham lam O(N log N): du an co loi (b >= a) lam truoc, sap theo a tang dan;
// du an co lo (b < a) lam sau, sap theo b giam dan
void sub2() {
vector<int> gains, losses;
for (int i = 0; i < n; i++) {
if (b[i] >= a[i]) gains.push_back(i);
else losses.push_back(i);
}
sort(gains.begin(), gains.end(), [&](int x, int y) { return a[x] < a[y]; });
sort(losses.begin(), losses.end(), [&](int x, int y) { return b[x] > b[y]; });
vector<int> ord = gains;
ord.insert(ord.end(), losses.begin(), losses.end());
cout << needFor(ord) << "\n";
}
int main() {
freopen("PRJCHAIN.INP", "r", stdin);
freopen("PRJCHAIN.OUT", "w", stdout);
cin >> n;
a.resize(n);
b.resize(n);
for (auto& x : a) cin >> x;
for (auto& x : b) cin >> x;
if (n <= 8) sub1();
else sub2();
return 0;
}
Bình luận