Hướng dẫn giải của Xóa phần tử (KS THCS 05)
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 thao tác hoặc xóa hai số nhỏ nhất, hoặc xóa số lớn nhất. Nếu làm ~x~ thao tác loại một thì sẽ xóa ~2x~ số nhỏ nhất và ~k - x~ số lớn nhất. Thử mọi ~x \in [0; k]~ và chọn tổng còn lại lớn nhất.
Sub 1: Mô phỏng bằng multiset — ~O(k \cdot n \log n)~, dùng khi ~n \le 2000~
Với mỗi ~x~, mô phỏng các thao tác trên multiset rồi tính tổng còn lại.
Sub 2: Tiền tố và hậu tố — ~O(n \log n + k)~
Sắp xếp, lấy tổng tiền tố và tổng hậu tố. Tổng còn lại khi chọn ~x~ là tổng - tiền tố ~2x~ - hậu tố ~k - x~.
Chương trình hoàn chỉnh
Nếu ~n \le 2000~ dùng sub 1, còn lại dùng sub 2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, K;
vector<long long> a;
// Nhan xet: sau khi cac thao tac, phan tu bi xoa la mot "tien to" nho nhat (2x so nho nhat) va
// mot "hau to" lon nhat (K-x so lon nhat), voi x la so lan chon "xoa hai so nho nhat".
// Tong con lai = tong - (tong 2x so nho) - (tong K-x so lon). Thu moi x tu 0 den K.
// Sub 1: voi moi x, mo phong bang multiset roi tinh tong con lai. O(K * n log n), dung khi n <= 2000
void sub1() {
long long best = LLONG_MIN;
for (int x = 0; x <= K; x++) {
multiset<long long> ms(a.begin(), a.end());
for (int t = 0; t < x; t++) { // x lan: xoa hai so nho nhat
ms.erase(ms.begin());
ms.erase(ms.begin());
}
for (int t = 0; t < K - x; t++) { // K-x lan: xoa so lon nhat
ms.erase(prev(ms.end()));
}
long long s = 0;
for (long long v : ms) s += v;
best = max(best, s);
}
cout << best << "\n";
}
// Sub 2: sap xep, dung tong tien to va tong hau to, O(n log n)
void sub2() {
vector<long long> s = a;
sort(s.begin(), s.end());
vector<long long> pre(n + 1, 0);
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + s[i];
long long total = pre[n];
long long best = LLONG_MIN;
for (int x = 0; x <= K; x++) {
long long removedSmall = pre[2 * x]; // 2x so nho nhat
long long removedBig = total - pre[n - (K - x)]; // K-x so lon nhat
best = max(best, total - removedSmall - removedBig);
}
cout << best << "\n";
}
int main() {
freopen("DELK.INP", "r", stdin);
freopen("DELK.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n >> K;
a.assign(n, 0);
for (auto &x : a) cin >> x;
if (n <= 2000) sub1();
else sub2();
return 0;
}
Bình luận