[集训队互测 2023] 优惠购物

Luogu

IDLGP10001

Time1000ms

Memory2048MB

DifficultyP7

贪心线段树集训队互测2023

小 C 要购买 $n$ 个物品，这些物品有前置关系，必须**依次**购买（即在购买了第 $i$ 个后才能购买第 $i+1$ 个）。他初始有 $m$ 张优惠劵和无穷多个金币。每个物品有两个属性，价格 $a_i$ 和优惠劵的使用上限 $b_i(0\le b_i\le a_i)$。购买一个物品的流程如下： - 选择使用 $x(0\le x\le b_i)$ 张优惠券，付出 $a_i-x$ 个金币和 $x$ 张优惠券。 - 购买完后可得到 $\lfloor \frac{a_i-x}{c} \rfloor$ 张优惠券（即一次购买中，每付出 $c$ 个金币可以得到一张优惠券，$c$ 为给定常数）小 C 想求出最少花费多少个金币能购买全部物品。 ## Input 本题包含多组数据，第一行包含一个整数 $T$，表示数据组数。对于每组数据： - 第一行包含三个整数 $n,m,c$。 - 第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$ 表示每个物品的价格。 - 第三行包含 $n$ 个整数 $b_1,b_2,...,b_n$ 表示优惠劵的使用上限。 ## Output 对于每组数据输出一行： - 第一行输出一个整数，表示最少需要的金币数量。 [samples] ## Note 对于所有数据，$1\le \sum n\le 10^6,0\le m,a_i,b_i\le 10^9,2\le c\le 10^9$。 - Subtask 1 (5 pts)：$1\le T\le 5,1\le n\le 10,1\le m,\sum a_i,\sum b_i\le 10$ - Subtask 2 (10 pts)：$a_i=b_i$ - Subtask 3 (10 pts)：$1\le \sum n\le 500,1\le \sum m,\sum a_i,\sum b_i\le 500$ - Subtask 4 (10 pts)：$1\le \sum n\le 6000,1\le \sum m,\sum a_i,\sum b_i\le 6000$ - Subtask 5 (10 pts)：$1\le \sum n\le 6000$ - Subtask 6 (15 pts)：$1\le \sum n\le 2\times 10^5,2\le c\le 20$ - Subtask 7 (10 pts)：$1\le \sum n\le 1\times 10^6,2\le c\le 20$ - Subtask 8 (15 pts)：$1\le \sum n\le 2\times 10^5$ - Subtask 9 (15 pts)：$1\le \sum n\le 1\times 10^6$ 时间限制：$\texttt{1s}$ 空间限制：$\texttt{2048MB}$

Samples

Input #1

4
6 16 2
17 14 13 5 13 4
12 5 5 2 10 2
6 4 2
8 1 20 10 4 10
8 1 15 3 4 6
5 40 7
21 47 7 25 47 
9 26 4 4 39 
5 151 10
86 84 164 158 160
43 42 82 79 80

Output #1

Input #2

见附件 ex_shop2.in。

Output #2

见附件 ex_shop2.out。

API Response (JSON)

{
  "problem": {
    "name": "[集训队互测 2023] 优惠购物",
    "description": {
      "content": "小 C 要购买 $n$ 个物品，这些物品有前置关系，必须**依次**购买（即在购买了第 $i$ 个后才能购买第 $i+1$ 个）。 他初始有 $m$ 张优惠劵和无穷多个金币。每个物品有两个属性，价格 $a_i$ 和优惠劵的使用上限 $b_i(0\\le b_i\\le a_i)$。 购买一个物品的流程如下： - 选择使用 $x(0\\le x\\le b_i)$ 张优惠券，付出 $a_i-x$ 个金",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 2097152
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10001"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 C 要购买 $n$ 个物品，这些物品有前置关系，必须**依次**购买（即在购买了第 $i$ 个后才能购买第 $i+1$ 个）。\n\n他初始有 $m$ 张优惠劵和无穷多个金币。每个物品有两个属性，价格 $a_i$ 和优惠劵的使用上限 $b_i(0\\le b_i\\le a_i)$。\n\n购买一个物品的流程如下：\n\n- 选择使用 $x(0\\le x\\le b_i)$ 张优惠券，付出 $a_i-x$ 个金...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments