Nhận xét

Nếu Nura có thể mua đủ ~k~ món đồ chơi trong ~d~ ngày đầu tiên, thì Nura cũng có thể mua được chúng trong ~d+1~ ngày.

Ý tưởng

Với nhận xét trên, ta nghĩ đến việc chặt nhị phân tìm số ngày nhỏ nhất, rồi đưa bài toán về bài toán kiểm tra: "Với ~d~ ngày đầu tiên, Nura có thể mua được ~k~ món đồ chơi không?". Để kiểm tra, ta đi tìm chi phí nhỏ nhất để mua ~k~ món đồ chơi trong ~d~ ngày đầu, rồi kiểm xem nó có vượt quá ~s~ hay không.

Giả sử ta muốn mua ~x~ món đồ loại ~1~, và ~k-x~ món đồ loại ~2~. Dễ thấy, để tối thiểu chi phí, ta sẽ luôn chọn ~x~ món loại ~1~ rẻ nhất và mua vào ngày có ~a[i]~ nhỏ nhất trong ~d~ ngày đầu. Tương tự, ta sẽ chọn ~k-x~ món loại ~2~ rẻ nhất và mua vào ngày có ~b[i]~ nhỏ nhất trong ~d~ ngày đầu.

Cài đặt

Ta chia ~m~ món đồ chơi được rao bán vào hai mảng ~t1~ (dành cho loại ~1~), và ~t2~ (dành cho loại ~2~).

Để tính nhanh tổng ~x~ món rẻ nhất của từng loại, ta sắp xếp các mảng ~t1~ và ~t2~ theo giá trị tăng dần, rồi tạo các mảng tính tổng tiền tố trong ~O(n)~:

• ~sum1[i] = t1[i].cost + sum1[i-1]~ ~(0 < i \le t1.size())~.
• ~sum2[i] = t2[i].cost + sum2[i-1]~ ~(0 < i \le t2.size())~.

Để tìm ngày có tỉ giá nhỏ nhất ở mỗi loại trong ~i~ ngày đầu tiên, ta tính trước ~2~ mảng sau trong ~O(n)~:

• ~minDol[i] = d~, sao cho ~a[d] = min(a[1, 2, ..., i])~.
• ~minPou[i] = d~, sao cho ~b[d] = min(b[1, 2, ..., i])~.

Với mỗi ~d~ được xét: Ta duyệt ~x~ ~(0 \le x \le min(k, t1.size()))~ - cần mua ~x~ món đồ loại ~1~, và ~k-x~ món đồ loại ~2~. Nếu tổng chi phí thoả mãn không lớn hơn ~s~ (số tiền Nura có), thì ta sẽ cập nhật ~d~ vào kết quả và lưu lại ~x~ để in ra phương án, rồi tiếp tục chặt nhị phân đến hết.

Lưu ý: các phần tử của ~t1~ và ~t2~ nên được lưu hai giá trị là số thứ tự ban đầu và giá trị của món đồ, để có thể in ra phương án khi tìm được.

Độ phức tạp

Khi chặt nhị phân, để check khả năng mua được ~k~ món đồ, ta mất ~O(k)~ trong mỗi lần check. Vì vậy độ phức tạp là ~O(klogn)~.

Code tham khảo

#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, a, b) for(int i = (a), _b = (b); i >= _b; --i)
typedef long long ll;
typedef vector<int> vi;

int numDays, numToys, need, total;
const int N = 2e5+5;
int dol[N], pou[N];
struct Toy {
    int idx, cost;
    bool operator < (Toy const &a) const {
        return cost < a.cost;
    }
};
vector<Toy> t1, t2;
ll sum1[N], sum2[N];
int minDol[N], minPou[N];

void Input() {
    cin >> numDays >> numToys >> need >> total;
    FOR(i, 1, numDays) cin >> dol[i];
    FOR(i, 1, numDays) cin >> pou[i];
    FOR(i, 1, numToys) {
        int t, c; cin >> t >> c;
        if (t == 1) t1.pb({i, c});
        else t2.pb({i, c});
    }
}

int check(int maxDay) {
    int d = dol[minDol[maxDay]];
    int p = pou[minPou[maxDay]];
    if (need <= t2.size() && sum2[need-1]*p <= total) return 0;

    FOR(i, 0, min((int)t1.size(), need)-1) if (need-(i+1) <= t2.size()) {
        ll cost = 1ll*sum1[i]*d;
        if (i+1 < need) cost += 1ll*sum2[need-(i+1)-1]*p;
        if (cost <= total) return i+1;
    }
    return -1;
}

void Solve() {
    sort(t1.begin(), t1.end());
    sort(t2.begin(), t2.end());

    FOR(i, 0, (int)t1.size()-1) {
        sum1[i] = t1[i].cost;
        if (i) sum1[i] += sum1[i-1];
    }

    FOR(i, 0, (int)t2.size()-1) {
        sum2[i] = t2[i].cost;
        if (i) sum2[i] += sum2[i-1];
    }

    FOR(i, 1, numDays) {
        minDol[i] = i; minPou[i] = i;
        if (i > 1) {
            if (dol[minDol[i-1]] < dol[i]) minDol[i] = minDol[i-1];
            if (pou[minPou[i-1]] < pou[i]) minPou[i] = minPou[i-1];
        }
    }

    int L = 1, R = numDays;
    int minDay = R+1, numT1 = -1;
    while (L <= R) {
        int mid = (L+R) >> 1;
        int cur = check(mid);
        if (cur != -1) minDay = mid, numT1 = cur, R = mid-1;
        else L = mid+1;
    }

    if (minDay > numDays) cout << -1;
    else {
        cout << minDay << '\n';
        FOR(i, 0, numT1-1) {
            cout << t1[i].idx << ' ' << minDol[minDay] << '\n';
        }
        FOR(i, 0, need-numT1-1) {
            cout << t2[i].idx << ' ' << minPou[minDay] << '\n';
        }
    }
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(0); cin.tie(0);
    Input(), Solve();
    return 0;
}