糖果店

【题意简述】

有 $n$ 颗糖果，第 $i$ 颗糖果的价格为 $a_i$。至多使用 $k$ 个礼盒，每个礼盒装入两颗糖果，并只支付其中较贵者的价格。给定预算 $m$，求最多能够购买多少颗糖果。

【数据点 1∼31\sim 31∼3】

【题目描述】

这一档保证 $n\leq 10$。

【Hint】

每颗糖果有三种状态：不购买、单独结算、装入礼盒。枚举后检查礼盒是否能够两两配对。

【解法】

枚举购买集合，再枚举其中哪些糖果进入礼盒。对于一颗尚未结算的糖果，可以单独购买，也可以选择另一颗尚未结算的糖果与它组成礼盒。

检查总费用是否不超过 $m$，取所有合法方案中购买数量的最大值。时间复杂度可以做到 $\mathcal{O}(3^n n)$，空间复杂度为 $\mathcal{O}(n)$。

【数据点 4∼94\sim 94∼9】

【题目描述】

数据点 $4\sim 6$ 保证 $k=0$；数据点 $7\sim 9$ 保证 $k\leq 1$。

【Hint】

先固定购买数量 $x$。应当选择哪些糖果？若只能使用一个礼盒，又应当把哪两颗糖果放入礼盒？

【解法】

将价格排序为 $a_1\leq a_2\leq\cdots\leq a_n$。当 $k=0$ 时，购买 $x$ 颗糖果的最小费用为

当 $k=1$ 且 $x\geq 2$ 时，把所选糖果中最贵的两颗装入礼盒，可以省去其中较便宜者的价格，最小费用为

这一档已经说明：固定购买集合以后，应优先把较贵的糖果放入礼盒。

【数据点 10∼1510\sim 1510∼15】

【题目描述】

这一档允许使用多个礼盒，但 $n$ 的范围仍允许逐个计算每种购买数量的费用。

【Hint】

固定购买数量 $x$，令

价格均为正数，因此使用满 $r$ 个礼盒一定不劣。

【解法】

选择最贵的 $2r$ 颗糖果装入礼盒，再把它们按照价格相邻配对。直接枚举 $x$，并用 $\mathcal{O}(x)$ 的时间计算费用，总时间复杂度为 $\mathcal{O}(n^2)$。

【正解】

【题目描述】

对每个 $x$ 求购买恰好 $x$ 颗糖果的最小费用，并判断它是否不超过 $m$。

【Hint】

证明三件事：

1. 只需购买排序后的前 $x$ 颗糖果；
2. 礼盒中装入最贵的 $2r$ 颗糖果；
3. 这 $2r$ 颗糖果按照价格相邻配对。

【解法】

任意购买方案中的价格从小到大记为 $c_1,c_2,\ldots,c_x$。全体糖果排序后有 $a_i\leq c_i$。单独结算与礼盒结算都只会取一个价格或两个价格的最大值，因此把每个 $c_i$ 替换成不大的 $a_i$ 不会增加费用。故存在一个最优方案，购买的恰好是前 $x$ 颗糖果。

若某颗较便宜的糖果在礼盒中，而一颗更贵的糖果单独结算，交换二者不会增加费用。因此可以令最贵的 $2r$ 颗糖果全部进入礼盒。

对于 $a\leq b\leq c\leq d$，相邻配对的费用为 $b+d$，另外两种配对的费用均为 $c+d$。不断消去最小的四颗待配对糖果，即可得到排序后相邻配对最优。

令 $L=x-2r$。前 $L$ 颗糖果单独结算，后 $2r$ 颗糖果相邻配对，因此

第二项只取区间 $(L,x]$ 中与 $x$ 奇偶性相同的位置。分别维护普通前缀和、奇数位置前缀和与偶数位置前缀和，即可在 $\mathcal{O}(1)$ 时间内计算 $\operatorname{Cost}(x)$。

【复杂度分析】

排序的时间复杂度为 $\mathcal{O}(n\log n)$，枚举购买数量的时间复杂度为 $\mathcal{O}(n)$，空间复杂度为 $\mathcal{O}(n)$。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/244Name:candy.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 50001011using namespace std;12int T,n,k,Line[MAXN];13long long m,Pre[MAXN],Odd[MAXN],Even[MAXN];14long long Calc(int x){15    int Count=min(k,x/2),Left=x-Count*2;16    long long Ret=Pre[Left];17    if(x&1) Ret+=Odd[x]-Odd[Left];18    else Ret+=Even[x]-Even[Left];19    return Ret;20}21void Solve(){22    scanf("%d%lld%d",&n,&m,&k);23    for(int i=1;i<=n;i++) scanf("%d",&Line[i]);24    sort(Line+1,Line+n+1);25    Pre[0]=Odd[0]=Even[0]=0;26    for(int i=1;i<=n;i++){27        Pre[i]=Pre[i-1]+Line[i];28        Odd[i]=Odd[i-1];Even[i]=Even[i-1];29        if(i&1) Odd[i]+=Line[i];30        else Even[i]+=Line[i];31    }32    int Ans=0;33    for(int i=1;i<=n;i++){34        if(Calc(i)<=m) Ans=i;35    }36    printf("%d\n",Ans);37    return;38}39int main(){40    int c;41    scanf("%d%d",&c,&T);42    while(T-->0) Solve();43    return 0;44}