清仓甩卖

【题意简述】

有 $n$ 件物品，第 $i$ 件物品的原价为 $w_i$，清仓价格为 $v_i\in\{1,2\}$。在清仓价格总和不超过 $m$ 的条件下，求能够得到的最大原价总和。

【数据点 1∼41\sim 41∼4】

【题目描述】

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

【Hint】

直接枚举购买集合。

【解法】

枚举全部 $2^n$ 个集合，计算每个集合的清仓价格之和与原价之和，保留总价格不超过 $m$ 的方案。时间复杂度为 $\mathcal{O}(n2^n)$，空间复杂度为 $\mathcal{O}(n)$。

【数据点 5∼125\sim 125∼12】

【题目描述】

数据点 $5\sim 8$ 保证所有清仓价格均为 $1$；数据点 $9\sim 12$ 保证所有清仓价格均为 $2$。

【Hint】

当所有物品的清仓价格相同时，只需要决定购买数量。

【解法】

若所有清仓价格均为 $1$，至多购买 $\min(n,m)$ 件物品；若均为 $2$，至多购买 $\min(n,\lfloor m/2\rfloor)$ 件物品。两种情况下都应选择原价最大的若干件。

将原价从大到小排序后取前若干项之和，时间复杂度为 $\mathcal{O}(n\log n)$。

【数据点 13∼1913\sim 1913∼19】

【题目描述】

这一档同时出现两类物品。

【Hint】

分别对清仓价格为 $1$ 与 $2$ 的物品排序，再枚举购买多少件第二类物品。

【解法】

枚举购买 $x$ 件清仓价格为 $2$ 的物品，剩余预算为 $m-2x$，再购买至多 $m-2x$ 件清仓价格为 $1$ 的物品。

直接累加每次选择的物品价值，时间复杂度为 $\mathcal{O}(n^2)$。当前瓶颈只在重复计算两类物品的前若干项之和。

【正解】

【题目描述】

对每种可能的两类物品数量组合求最大价值。

【Hint】

对两类物品分别维护原价的降序前缀和。

【解法】

将清仓价格为 $1$ 与 $2$ 的物品按照原价从大到小排列，分别记为序列 $A,B$，并维护前缀和 $S_A,S_B$。

固定购买 $x$ 件第二类物品时，选择 $B$ 的前 $x$ 件一定不劣。此时还能购买

件第一类物品，同样应选择 $A$ 的前 $y$ 件。当前方案的价值为

任意合法方案都对应某个 $x$。固定 $x$ 后，将两类物品分别替换成原价最大的同样件数，不会改变总价格，只会使总价值不减。因此枚举覆盖了某个最优方案。

【复杂度分析】

排序的时间复杂度为 $\mathcal{O}(n\log n)$，枚举的时间复杂度为 $\mathcal{O}(n)$，空间复杂度为 $\mathcal{O}(n)$。前缀和与答案需要使用 long long。

【参考代码】

1/*2Author:Ehundategh3Date:2026/7/244Name:sale.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define MAXN 50001011using namespace std;12int T,n,m,Value[MAXN],Type[MAXN],One[MAXN],Two[MAXN];13long long PreOne[MAXN],PreTwo[MAXN];14bool cmp(int a,int b){return a>b;}15void Solve(){16    scanf("%d%d",&n,&m);17    for(int i=1;i<=n;i++) scanf("%d",&Value[i]);18    for(int i=1;i<=n;i++) scanf("%d",&Type[i]);19    int CntOne=0,CntTwo=0;20    for(int i=1;i<=n;i++){21        if(Type[i]==1) One[++CntOne]=Value[i];22        else Two[++CntTwo]=Value[i];23    }24    sort(One+1,One+CntOne+1,cmp);25    sort(Two+1,Two+CntTwo+1,cmp);26    PreOne[0]=PreTwo[0]=0;27    for(int i=1;i<=CntOne;i++) PreOne[i]=PreOne[i-1]+One[i];28    for(int i=1;i<=CntTwo;i++) PreTwo[i]=PreTwo[i-1]+Two[i];29    long long Ans=0;30    for(int i=0;i<=CntTwo&&i*2<=m;i++){31        int Count=min(CntOne,m-i*2);32        Ans=max(Ans,PreTwo[i]+PreOne[Count]);33    }34    printf("%lld\n",Ans);35    return;36}37int main(){38    int c;39    scanf("%d%d",&c,&T);40    while(T-->0) Solve();41    return 0;42}