专栏文章

题解：CF1282B2 K for the Price of One (Hard Version)

OOIerJiang_1017
CF1282B2题解参与者 1已保存评论 0

文章操作

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

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

CF1282B2

题目大意

有 nn 个商品，每种商品都有价格 aia_i，每种商品只能购买一次。现在买一个物品，可以免费拿走价格低于它的 k−1k - 1 个物品，但当比它价格小的商品不足 k−1k - 1 个时，此优惠无效。给定总钱数，求能购买的最多物品数量。

解决思路

根据课上老师讲的思路我自己的推导，我想到了贪心并得到了两个 DP 公式：
  • 若 i<ki < k，则 zi=zi−1+aiz_i = z_{i - 1} + a_i；
  • 若 i≥ki \geq k，则 zi=zi−k+aiz_i = z_{i - k} + a_i。
然后就好说了，枚举上述式子中的 zz 数组，当 zi≤pz_i \leq p 时，ii 即为答案。

代码展示

CPP
#include <iostream>
#include <algorithm>
#include <cstring>
//不用万能头，从我做起
using namespace std;

sont int N = 3e6 + 80;
int t, n, p, k, a[N], z[N], ans;

int main()
{
	ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);//减少输入时间
	cin >> t;
	while(t--)
	{
		ans = 0;
		cin >> n >> p >> k;
		for(int i = 1; i <= n; i++)
			cin >> a[i];
		sort(a + 1, a + n + 1);//从小到大排序
		for(int i = 1; i <= n; i++)
			z[i] = 0x3f3f3f3f;//代替memset,全部赋值
		for(int i = 1; i <= n; i++)
		{//分情况讨论 
			if(i >= k) z[i] = min(z[i], z[i - k] + a[i]);
			z[i] = min(z[i], z[i - 1] + a[i]);
		}
		for(int i = 1; i <= n; i++)
			if(z[i] <= p) ans = i;//枚举最终答案
		cout << ans << endl;
	}

评论

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

正在加载评论...