专栏文章

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

__miss_
B4104题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miqnfl17
此快照首次捕获于
2025/12/04 07:39
3 个月前
此快照最后确认于
2025/12/04 07:39
3 个月前
查看原文

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

题意

题意很明确，就不过多赘述了。

Solution

首先需要发现优惠券可转化为 mm 件物品打包成了一个价格为 ww 的物品，因此只要把它和先前 mm 件物品的总和比较，贪心的取最小即可。
实现就是先降序排列（大的尽量多用优惠劵），然后遍历序列，mm 个数分一组统计总和与 ww 比较，选更小的就行。
记得开 long long。

Code

CPP
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,w,cnt,ans;
int a[200010];
signed main(){
	cin>>n>>m>>w;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	sort(a+1,a+1+n,greater<int>());//从大到小排序
	for(int i=1;i<=n;++i){
		cnt+=a[i];
		if(i%m==0){
			if(cnt>w) ans+=w;
			else ans+=cnt;
			cnt=0;
		}
	}
	if(cnt>w) ans+=w;
	else ans+=cnt;
	cout<<ans;
	return 0;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...