自动搬运

查看原文

来自洛谷，原作者为

	Wendy_Hello_qwq ^v^ || 1.3 || ENFJ-A || 代词使用她/梦璃 || 学术开，有事请找 Mengli_Wendy_qwq 谢谢 || 用乐观的心态去拥抱生活

搬运于2025-08-24 21:17:08，当前版本为作者最后更新于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 记录。

完结撒花。

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