满减划算还是折扣划算
概述
给你 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: 满减划算还是折扣划算