满减划算还是折扣划算

    
        标签：
        
            笔试算法题
        
    发布于：2022-03-19 12:51:26
    编辑于：2022-03-22 21:43:20
    浏览量：1204

概述

给你 n 个价格，n 个折扣后价格，m 个满减规则，要求折扣和满减只能搞一个，问你哪个划算。

暴力法

听 JW 说直接暴力 m 个满减规则就能 AC，也不超时。

时间复杂度 O(nm)。

最优价格法

首先，对每个满减规则（设满 c 减 d）记录其最优价格，方法是从小的 c 开始，同时维护一个 maxD，哈希表里记录 c = max(d, maxD)。同时也更新 maxD = c。

之后，二分搜索寻找第一个不大于目标价格的第一个满减价格，总的复杂度 O(nlogm)。

或者，考虑到让我们求得价格是递增的特点，所以直接遍历最优满减即可，总的复杂度为 O(max(n, m))。

然后就过了 18%，郁闷。

最后两分钟时我担心可能是我二分搜索用错了，（实际上就是用错了，lower_bound() 给出的是不小于目标值的第一个元素，而非不大于目标值的第一个元素），所以我换了遍历解法，结果刚刚复盘的时候才发现 while 循环里少写了 = 。

哇，我哭了。

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

struct cd {
    int c, d;
};

int main() {
    int n; cin >> n;
    vector<int> prices(n);
    for (int i = 0; i < n; i ++) {
        cin >> prices[i];
    }
    vector<int> discounts(n);
    for (int i = 0; i < n; i ++) {
        cin >> discounts[i];
    }
    int m; cin >> m;
    vector<cd> cds(m);
    for (int i = 0; i < m; i ++) {
        cin >> cds[i].c;
    }
    for (int i = 0; i < m; i ++) {
        cin >> cds[i].d;
    }
    sort(cds.begin(), cds.end(), [](const cd& a, const cd& b)->bool {
        if (a.c != b.c) {
            return a.c < b.c;
        } else {
            return a.d > b.d;
        }
    });
    unordered_map<int, int> map;
    for (auto& t : cds) {
        map[t.c] = max(map[t.c], t.d);
    }
    vector<int> cdPrices;
    for (auto & iter : map) {
        cdPrices.push_back(iter.first);
    }
    sort(cdPrices.begin(), cdPrices.end());  // asc
    int preMax = 0;
    for (auto cdPrice : cdPrices) {
        map[cdPrice] = max(preMax, map[cdPrice]);
        preMax = map[cdPrice];
    }

    int price = 0;
    int discount = 0;
    int idx = 0;
    for (int i = 0; i < n; i ++) {
        price += prices[i];
        discount += discounts[i];
        while (idx < cdPrices.size() && cdPrices[idx] <= price) idx ++;
        int cdPrice = price;
        if (idx != 0) {
            cdPrice = price - map[cdPrices[idx-1]];
        }
        if (discount == cdPrice) {
            cout << "B";
        } else if (discount < cdPrice) {
            cout << "Z";
        } else {
            cout << "M";
        }
    }
}

Links: 满减划算还是折扣划算