有一个问题:有 n 个产品,以及 m 个优惠券,如果原始价格至少为 l 卢布,则第 i 个优惠券可以让您将一件商品的成本减少 d。我编写了一个解决方案,其中我对 的对数组进行排序di,之后我使用搜索箱来查找成本最低的产品,其价格至少为li卢布,然后我删除数组的这个元素并添加一个新的价格至 ans。显然问题出在删除上,但我不知道如何做到这一点,以便多个优惠券对同一产品无效。
第一行包含整数 n 和 m (1 ≤ n, m ≤ 2⋅10^5) — 商品和优惠券的数量。
第二行列出数字 c (1 ≤ ci ≤ 10^9) — 物品的成本。
第三行列出了数字 l (1 ≤ li ≤ 10^9) - 使用优惠券的商品的最低价格。
第四行列出数字d(1≤di≤li)——使用优惠券后的折扣。
#include <iostream>
#include <vector>
#include <algorithm>
#define len(a) ((int)((a).size()))
using namespace std;
bool cmp(const pair<int, int>& f, const pair<int, int>& s) {
if (f.first != s.first)
return f.first < s.first;
return f.second > s.second;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
vector<int> c(n);
vector<pair<int, int>> ld(m);
for (int i = 0; i < n; ++i) cin >> c[i];
for (int i = 0; i < m; ++i) cin >> ld[i].first;
for (int i = 0; i < m; ++i) cin >> ld[i].second;
stable_sort(ld.begin(), ld.end(), cmp);
stable_sort(c.begin(), c.end());
int i = 0, j = 0;
while (i < n && j < m) {
if (c[i] >= ld[j].first) {
c[i] -= ld[j].second;
++j;
}
++i;
}
long long ans = 0;
for (auto& num : c) ans += num;
cout << ans;
return 0;
}
Входные данные:
10 5
9 7 1 5 2 2 5 5 7 6
7 2 7 8 2
3 2 4 1 2
Ответ:
37
如果贪心算法(
минимально стоящий товар, цена которого хотя бы li рублей)有效,则无需删除任何内容。只需并行遵循两个向量(产品和折扣)并将收益相加即可。
当找到合适的产品时,在两个向量中提升索引,如果价格不足,则仅在产品向量中提升索引。