B1. K for the Price of One (Easy Version)（贪心）

 

商店里有 n 样物品，你有 p 元钱，你可以买一个物品付a[i]元 或者 买k个物品(这个优惠政策可以一直使用)，只付最贵的那个。 每个物品最多买一次，求最多能买多少物品。

 

思路：先将商品价格排序，利用贪心，求出 sum[i]，及前缀和。当然价格少的，我们全部都要，这样我们定义 sum[i]=sum[i-k]+a[i] (i>=k) 表示买到第 i 件商品为止，所要的价格，这样利用滚动数组 算法复杂度 O（n）

 

const int N=2e5+5; int n,m,t; int i,j,k; int a[N]; int sum[N]; int main() { //IOS; rush(){ int n,p,k; sdd(n,p); sd(k); for(i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); sum[1]=a[1]; for(i=k;i<=n;i++) sum[i]=sum[i-k]+a[i]; int pos=upper_bound(sum,sum+1+n,p)-sum; //if(sum[pos]>p) pos--; pos--; pd(pos); } //PAUSE; return 0; }

当然可以采用 dp 的方法，或者对代码有问题的可以看一下 B2 的实现方法，加强理解

K for the Price of One (Hard Version)（dp/贪心）