专栏文章

题解：P14293 [JOI2024 预选赛 R2] 购物 2 / Shopping 2

封封禁用户
P14293题解参与者 1已保存评论 0

文章操作

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

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

题目大意：

传送门
JOI 商店有 NN 件商品，每件商品有价格和种类。促销活动持续 MM 天，第 jj 天所有种类为j的商品打 55 折。有 QQ 位顾客，每位顾客在第 TkT_k 天购买编号在 [Lk,Rk][L_k, R_k] 范围内的所有商品。需要计算每位顾客的总花费。

题目思路：

显然要用前缀和，不会戳这里，应该都会。
很显然，答案就是：
  • 区间内所有商品原价总和 −- 第 tkt_k 天区间内种类为 tkt_k 的商品的原价一半。
前半部分就可以用前缀和 ff 在 O(1)O(1) 快速求出，那就会有人问了，后面呢怎么算呢？
其实也是前缀和思想，我们定义：
  • it[i]it[i] 为所有种类为 ii 的商品编号，按升序排序。
  • s[i][j]s[i][j] 表示种类 ii 的前 jj 个商品的半价总和。
利用前缀和思想，可以预处理出第 jj 类商品在任意子区间的半价总和，显然公式为：
  • s[i][j+1]=s[i][j]+p[it[i][j]]÷2s[i][j+1]=s[i][j] + p[it[i][j]] \div 2
注：p[i]p[i] 为商品 ii 的定价。
后面统计时候，使用二分找到找到第一个可以享受折扣的商品 ll 和找到最后一个可以享受折扣的商品 rr，右半部分答案就为 s[tk][r+1]−s[tk][l]s[t_k][r+1]-s[t_k][l]，整题答案就是 f[rk]−f[lk−1]−(s[tk][r+1]−s[tk][l])f[r_k]-f[l_k-1]-(s[t_k][r+1]-s[t_k][l])，这题就写完了。
注：f[i]f[i] 为商品 ii 的定价 pip_i 的前缀和。
思路讲得很清楚，代码就不放了。

评论

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

正在加载评论...