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

OIerJiang_1017 · 2025-01-19 11:26:16 · 题解

CF1282B2

题目大意

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

解决思路

根据课上老师讲的思路我自己的推导，我想到了贪心并得到了两个 DP 公式：

• 若 i < k，则 z_i = z_{i - 1} + a_i；
• 若 i \geq k，则 z_i = z_{i - k} + a_i。

然后就好说了，枚举上述式子中的 z 数组，当 z_i \leq p 时，i 即为答案。

代码展示

#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;
    }