Morris' Blog 我在摸索我存在的意義、生命的意義、內涵及價值。 沒有真正神手般的厲害，套用模式是大部分的情況。 沒那麼厲害的我存在的意義為何，襯托出神的存在？ 有時候不能怪別人不給我機會，我已經開始省思， 為什麼我沒有給別人機會的原因，而是全要靠別人。 有時候我認為我與眾不同，那是因為我做不到很多人能辦到的事情。 我聽不到、玩不起來、說得不夠明瞭、理解得不夠多， 我缺少的語文能力，就是一切一切無能的判定。 為此，我不曉得能做些對別人有幫助的事情。 我知道我自己是個不服輸的性格，但現在我不得不認輸。 我沒有能力，因此我必須認輸。 我到底來這世界作什麼？處處充滿不確定性， 而我總是無法出類拔萃，想當個一般人似乎也回不了頭了。 越強大的挑戰需要越強力的支持，而我的支持是什麼？ 最近嘗試與人談話，但都是失敗的結局，沒人能接受， 不需要言語，不需要溝通，一切所想都表達不出來。

49愛的鼓勵 6訂閱站台

Description

現在有 N 個產品，帶 M 元去購物。
每個產品有兩個價錢，分別為原價和打折後的價錢。

現在有 K 次打折機會，求在 M 元內最多能買多少產品回去。

Input Format

輸入的第一行有一個正整數 T，代表測試資料的組數。

每組測資的第一行有三個整數 N, K, M (1 <= K <= N <= 100,000, M <= 10^15)。

接下來有 N 行，每行有兩個整數 C[i], D[i] (1 <= D[i] <= C[i] <= 10^9)，表示該產品的原價和打折後的價錢。

Output Format

對於每組測資輸出一行整數，購買產品的最大數量。

Sample Input

23 0 61 12 23 34 1 73 22 28 14 3

Sample Output

33

---

解法 by inker.



#include <stdio.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
#define MAX_N 100005
struct zkwST {
    int M;
    pair<long long, int> st[262144 + 10];
    pair<long long, int> elem[131072 + 10];
    zkwST() {
    }
    void build(int n) {
        for(M = 1; M < n+1; M <<= 1);
        for(int i = 2*M-1; i > 0; i--) {
            if(i >= M) {
                if(i - M > n)   
                    st[i] = make_pair(0, 0);
                else
                    st[i] = elem[i - M];
            } else {
                st[i].first  = st[i<<1].first  + st[i<<1|1].first;
                st[i].second = st[i<<1].second + st[i<<1|1].second;
            }
        }
    }
    pair<long long, int> prefixQuery(long long S) {
        pair<long long, int> ret = make_pair(0LL, 0);
        int s;
        for(s = 1; s < M; ) {
            if(st[s<<1].first <= S) {
                ret.first  += st[s<<1].first;
                ret.second += st[s<<1].second;
                S -= st[s<<1].first;
                s = s<<1|1;
            } else {
                s = s<<1;
            }
        }
        if(st[s].first <= S) {
            ret.first  += st[s].first;
            ret.second += st[s].second;
        }
        return ret;
    }
    void singleUpdate(int index, pair<long long, int> val) {
        st[index + M] = elem[index] = val;
        for(int s = (index + M)>>1; s > 0; s >>= 1) {
            st[s].first  = st[s<<1].first  + st[s<<1|1].first;
            st[s].second = st[s<<1].second + st[s<<1|1].second;
        }
    }
};

int C[MAX_N], D[MAX_N];
int A[MAX_N], B[MAX_N], mapB[MAX_N];
int N, K;
long long M;
zkwST segTree;
bool cmpD(int i, int j) {
    return D[i] < D[j];
}
bool cmpC(int i, int j) {
    return C[i] < C[j];
}
struct cmpPQ {
    bool operator()(pair<int, int> &a, pair<int, int> &b) const {
        return a.first > b.first;
    }
};
int main() {
    int testcase;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%d %d", &N, &K);
        scanf("%lld", &M);
        for(int i = 0; i < N; i++) {
            scanf("%d %d", &C[i], &D[i]);
            A[i] = B[i] = i;
        } // Di <= Ci
       
        sort(A, A + N, cmpD);
        sort(B, B + N, cmpC);
       
        // build no-sale price with prefix-interval-query struct.
        for(int i = 1; i <= N; i++) {
            mapB[B[i-1]] = i;
            segTree.elem[i] = make_pair((long long)C[B[i-1]], 1);
        }
        segTree.build(N);
       
        // sweeping by sale price (small to large)
        priority_queue< pair<int, int>, vector< pair<int, int> > , cmpPQ > pQ;
            // pQ maintain size() <= K
        int ret = segTree.prefixQuery(M).second;
        long long pQcost = 0;
        for(int i = 0; i < N; i++) {
            pQcost += D[A[i]]; // add sale price
            pQ.push(make_pair(C[A[i]] - D[A[i]], A[i])); // <different price, index>
            if(pQ.size() > K) {
                pair<int, int> p = pQ.top();
                pQ.pop();
                pQcost += p.first;
            }
            segTree.singleUpdate(mapB[A[i]], make_pair(0, 0));
            if(pQcost > M)
                break;
            ret = max(ret, segTree.prefixQuery(M - pQcost).second + i+1);
        }
        printf("%d\n", ret);
    }
    return 0;
}
/*
100

10 9 819
54 49
95 43
89 40
89 84
64 60
69 58
99 88
78 34
83 62
93 77


10 1 267
52 25
51 17
88 58
86 82
61 55
38 33
36 2
97 44
100 100
85 1

4 2 15
20 3
40 4
50 7
8 8

4 1 11
20 3
40 4
50 7
8 8

4 2 15
20 3
40 4
50 7
8 8
*/