题解：B4104 [CSP-X2024 山东] 购物

Wendy_Hello_qwq · 2024-12-28 13:55:06 · 题解

题目传送门。

原文食用效果更佳。

题意

给定 n,m,w，分别表示 n 件物品，满 m 件商品可以使用优惠券和 w 价格的优惠券，买了优惠券只需要付优惠券的价格 w，这 m 个物品免费。求购买 n 件物品的最小价格。

分析

一道贪心题。

贪心需要排序，先将物品价格从小到大排序，然后倒序贪心。

设定一个 num，每一次都加上第 i 件物品的价格。再设定一个 cnt，记录当前有了几个物品。接着判断有没有满 m 个物品，满了的话，判断这 m 个物品是用优惠券便宜(小)，还是原价便宜(小)，加上较小的价格，算完后记得清零重新开始。最后循环外再判断一次，输出答案就可以了。

注意记得开 long long，数据范围较大。

Code

#include <cstdio>
#include <algorithm>
using namespace std;
// 数据范围较大，要开 long long 
long long num, cnt, ans;
long long n, m, w, a[200005];
int main() {
    scanf ("%lld%lld%lld", &n, &m, &w);
    for (int i = 1; i <= n; i++) scanf ("%lld", &a[i]);
    // 贪心，排序 
    sort (a + 1, a + 1 + n);
    // 倒序查找贪心 
    for (int i = n; i >= 1; i--) {
        // 价格 
        num += a[i];
        // 买了多少个商品 
        cnt++;
        // 当足够 m 件商品时 
        if (cnt == m) {
            // 答案取现在的价格总和与优惠券价格的最小值 
            ans = ans + (num < w ? num : w);
            // 全部归零 
            num = cnt = 0;
        }
    }
    // 最后再进行一次比较
    ans = ans + (num < w ? num : w);
    printf ("%lld", ans);
    return 0;
}

AC 记录。

完结撒花。

作者写题解不易，点个赞再走呗。