满减划算还是折扣划算

Tag: 笔试算法题 Posted on 2022-03-19 12:51:26 Edited on 2022-03-22 21:43:20 Views: 147

概述

给你 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";
        }
    }
}

未经允许,禁止转载,本文源站链接:https://iamazing.cn/