购物
2021/8/26 23:08:14
本文主要是介绍购物,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目大意
有 \(n\) 件商品,每一件商品价格为 \(P_i\) 个单位。
现在你手中共有 \(m\) 个单位的现金,以及 \(k\) 张优惠券。
你可以在购买某件商品时,使用至多一张优惠券,若如此做,该商品的价格会下降至 \(Q_i\)。
请问你至多能购买多少件商品。
解题思路
考虑贪心,先不考虑有没有优惠卷的情况肯定是从小到大买,这样一定会买的最多的。
按照这个思想,每一次买的时候就找最小的。
有两种情况:
- 使用了优惠券之后获得了一个最小值。
- 没有使用优惠券的最小值。
分别对 \(p\) 和 \(q\) 进行排序。
每次找最小的。
还要将用来优惠券的那些东西按照 \(p_i − q_i\) 放到堆里面,为以后撤销优惠券使用。
这就是反悔贪心。
AC CODE
#include <cstdio> #include <queue> #include <algorithm> using namespace std; #define int long long const int maxn = 1e6 + 5; struct node { int p, q; bool operator < (const node& rhs) const { return p - q > rhs.p - rhs.q; } } a[maxn]; int n, k, ans; long long m; priority_queue<node> Q; bool cmp(node a, node b) { if(a.q != b.q) return a.q < b.q; return a.p < b.p; } bool CMP(node a, node b) { return a.p < b.p; } signed main() { scanf("%lld%lld%lld", &n, &k, &m); for (int i = 1; i <= n; i++) scanf("%lld%lld", &a[i].p, &a[i].q); sort(a + 1, a + n + 1, cmp); for (int i = 1; i <= k; i++) { m -= a[i].q; Q.push(a[i]); if (m < 0) { printf("%lld\n", i - 1); return 0; } } ans = k; sort(a + k + 1, a + n + 1, CMP); for (int i = k + 1; i <= n; i++) { int tp = Q.top().p, tq = Q.top().q; if (a[i].p - a[i].q > tp - tq && a[i].q + tp - tq <= m) { m -= (a[i].q + tp - tq); ans++, Q.pop(), Q.push(a[i]); } else if (a[i].p <= m) ans++, m -= a[i].p; } printf("%lld\n", ans); return 0; }
这篇关于购物的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)