Java教程

购物

本文主要是介绍购物,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目大意

有 \(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;
}
这篇关于购物的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!