Lời giải

Dù dùng phiếu thế nào, mỗi sản phẩm hoặc được trả đúng giá, hoặc được miễn phí. Gọi ~F~ là tập các sản phẩm được miễn, khi đó chi phí bằng

~\sum_{i=1}^{n} a_i - \sum_{i \in F} a_i.~

Tổng ~\sum a_i~ không đổi, nên ta chỉ cần làm cho tổng giá các sản phẩm được miễn lớn nhất có thể.

Ta xét trường hợp chỉ có một phiếu giá trị ~x~. Sản phẩm được miễn là sản phẩm rẻ nhất trong nhóm, nên muốn nó đắt nhất có thể, ta chọn ~x~ sản phẩm đắt nhất. Khi đó sản phẩm được miễn là sản phẩm đắt thứ ~x~. Nếu chọn một nhóm khác, trong nhóm có ít nhất một sản phẩm nằm ngoài ~x~ sản phẩm đắt nhất, nên sản phẩm rẻ nhất của nhóm không thể đắt hơn sản phẩm đắt thứ ~x~.

Khi có nhiều phiếu, ta sắp giá giảm dần ~a_1 \ge a_2 \ge \cdots \ge a_n~ và cho các nhóm lần lượt lấy sản phẩm từ đầu mảng. Nếu dùng các phiếu ~x_1, x_2, \ldots, x_j~ theo thứ tự đó, nhóm thứ nhất gồm ~a_1, \ldots, a_{x_1}~ và miễn ~a_{x_1}~, nhóm thứ hai gồm ~x_2~ sản phẩm tiếp theo và miễn ~a_{x_1 + x_2}~, và cứ thế. Phiếu thứ ~i~ miễn sản phẩm ở vị trí ~x_1 + \cdots + x_i~.

Vị trí này càng lớn thì sản phẩm được miễn càng rẻ. Do đó ta muốn mọi tổng ~x_1 + \cdots + x_i~ đều nhỏ nhất có thể, và cách làm là dùng các phiếu theo thứ tự giá trị tăng dần: với mọi ~i~, tổng của ~i~ phiếu nhỏ nhất không vượt quá tổng của ~i~ phiếu bất kỳ.

Để thấy cách này tốt nhất, xét một phương án bất kỳ dùng ~j~ phiếu. Sắp các sản phẩm được miễn trong phương án đó theo giá giảm dần ~g_1 \ge g_2 \ge \cdots \ge g_j~, và gọi ~y_1, \ldots, y_j~ là kích thước các nhóm tương ứng. Mọi sản phẩm trong nhóm thứ ~k~ đều có giá ít nhất ~g_k~, và ~g_k \ge g_i~ khi ~k \le i~. Các nhóm không có sản phẩm chung, nên có ít nhất ~y_1 + \cdots + y_i~ sản phẩm có giá không nhỏ hơn ~g_i~. Nghĩa là

~g_i \le a_{\,y_1 + \cdots + y_i} \le a_{\,x_1 + \cdots + x_i},~

trong đó ~x_1 \le \cdots \le x_i~ là ~i~ phiếu nhỏ nhất trong cả ~k~ phiếu, nên ~x_1 + \cdots + x_i \le y_1 + \cdots + y_i~. Vế phải chính là sản phẩm mà cách tham lam miễn ở phiếu thứ ~i~. Vậy sản phẩm được miễn thứ ~i~ của tham lam không rẻ hơn sản phẩm được miễn thứ ~i~ của phương án kia. Ngoài ra, phương án kia dùng được ~j~ phiếu nên ~y_1 + \cdots + y_j \le n~, suy ra tổng ~j~ phiếu nhỏ nhất cũng không vượt quá ~n~, và tham lam cũng dùng được ít nhất ~j~ phiếu. Cộng lại, tổng giá tham lam miễn được không nhỏ hơn của phương án kia.

Khi cài đặt, ta duyệt các phiếu theo thứ tự tăng dần và giữ biến cur là số sản phẩm đã được xếp vào nhóm. Phiếu ~x~ tiếp theo dùng được khi cur + x <= n. Nếu phiếu này không vừa thì các phiếu sau, vốn không nhỏ hơn, cũng không vừa, nên ta dừng.

Với bộ test đầu tiên, giá sau khi sắp giảm dần là ~[18, 9, 7, 3, 2]~ và các phiếu sau khi sắp là ~[1, 1, 3]~. Phiếu ~1~ đầu tiên miễn ~18~, phiếu ~1~ thứ hai miễn ~9~, phiếu ~3~ gom ~\{7, 3, 2\}~ và miễn ~2~. Tổng được miễn là ~29~, nên chi phí là ~39 - 29 = 10~.

Chương trình

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

#ifdef JASPER
#include <debug.h>
#else
#define debug(...) 166
#endif

void solve() {
    int n, k;
    cin >> n >> k;
    vector<ll> a(n);
    vector<int> b(k);
    for (auto &x : a) cin >> x;
    for (auto &x : b) cin >> x;
    sort(a.rbegin(), a.rend());          // gia giam dan
    sort(b.begin(), b.end());            // phieu tang dan
    ll ans = accumulate(a.begin(), a.end(), 0LL);
    int cur = 0;
    for (int x : b) {
        if (cur + x > n) break;          // phieu lon hon cung khong vua
        ans -= a[cur + x - 1];           // san pham re nhat cua nhom
        cur += x;
    }
    cout << ans << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }

    return 0;
}

Độ phức tạp là ~O((n + k)\log(n + k))~ cho mỗi bộ test, bộ nhớ ~O(n + k)~. Trên test nặng nhất (~n = k = 2 \cdot 10^5~), chương trình chạy trong 0,04 s và dùng 12 MB, trong khi giới hạn là ~2~ s và ~256~ MB.

Lỗi thường gặp

• Nếu dùng phiếu lớn trước, phiếu lớn chiếm phần đầu mảng và đẩy sản phẩm được miễn của các phiếu nhỏ xuống sâu. Ở bộ test đầu tiên, thứ tự ~[3, 1, 1]~ chỉ miễn được ~7 + 3 + 2 = 12~ thay vì ~29~.
• Không thể chọn tùy ý sản phẩm được miễn. Nhóm phải có đúng ~x~ sản phẩm và chỉ sản phẩm rẻ nhất trong nhóm được miễn, nên muốn miễn một món đắt thì mọi món khác trong nhóm phải đắt hơn nó.
• Dùng continue thay cho break khi phiếu không vừa vẫn cho kết quả đúng, vì các phiếu sau đều lớn hơn. Nhưng nếu bỏ hẳn điều kiện cur + x <= n, chương trình sẽ truy cập ngoài mảng.
• Tổng giá có thể lên tới ~2 \cdot 10^5 \cdot 10^9 = 2 \cdot 10^{14}~, nên phải dùng long long.
• Có nhiều bộ test, nên mọi mảng và biến cur phải được khởi tạo lại. Cần đọc đủ ~k~ phiếu kể cả khi vòng lặp đã break.