Hướng dẫn giải của [VTT Q4 Contest 12] Bài 2: Xóa phần tử [DELK]
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 một số lớn nhất. Vì ~2k < n~ nên thứ tự các thao tác không ảnh hưởng đến tập số bị xóa: nếu có ~x~ thao tác kiểu "hai nhỏ nhất" thì đúng ~2x~ số nhỏ nhất và ~k-x~ số lớn nhất bị xóa.
Sub 1: Vét cạn — ~O(n \cdot k)~, dùng khi ~n \cdot k \le 2 \times 10^7~
Sắp xếp mảng tăng dần. Với mỗi ~x~ từ 0 đến ~k~, phần còn lại là đoạn từ vị trí ~2x~ đến vị trí ~n-(k-x)-1~; cộng trực tiếp đoạn đó bằng vòng lặp rồi lấy giá trị lớn nhất. Cách này đúng nhưng chậm khi ~n~ và ~k~ cùng lớn.
Sub 2: Tổng tiền tố — ~O(n \log n)~
Sau khi sắp xếp, tính mảng tổng tiền tố để lấy tổng mỗi đoạn trong ~O(1)~, nên việc thử mọi ~x~ chỉ tốn ~O(k)~. Chú ý dùng long long vì tổng có thể đến ~2 \times 10^{14}~.
Chương trình hoàn chỉnh
Hàm main đọc dữ liệu, sắp xếp, rồi gọi sub1 nếu ~n \cdot k~ nhỏ, ngược lại gọi sub2. 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;
long long a[200005], pre[200005];
// Sub 1: vét cạn — thử số lần x xóa "hai nhỏ nhất", tính lại tổng phần còn lại bằng vòng lặp
void sub1() {
long long best = 0;
for (int x = 0; x <= k; x++) {
long long s = 0;
for (int i = 2 * x; i < n - (k - x); i++) s += a[i];
best = max(best, s);
}
printf("%lld\n", best);
}
// Sub 2: dùng tổng tiền tố để tính tổng đoạn trong O(1)
void sub2() {
for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + a[i];
long long best = 0;
for (int x = 0; x <= k; x++)
best = max(best, pre[n - (k - x)] - pre[2 * x]);
printf("%lld\n", best);
}
int main() {
freopen("DELK.INP", "r", stdin);
freopen("DELK.OUT", "w", stdout);
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++) scanf("%lld", &a[i]);
// Thứ tự thao tác không quan trọng (vì 2k < n): sắp xếp rồi chỉ cần chọn x
sort(a, a + n);
if ((long long)n * k <= 20000000LL) sub1();
else sub2();
}
Bình luận