P15755 [JAG 2025 Summer Camp #1] JAG Box

传送门题目描述JAG Box 是一种目前在全世界流行的普通长方体盒子。共有N NN个 JAG Box。对于每个i 1 , 2 , … , N i 1, 2, \ldots, Ni1,2,…,N第i ii个盒子有一个整数重量A i A_iAi​。你将通过重复选择一个剩余的盒子并将其插入当前堆叠的最底部来建造一个垂直堆叠。当一个重量为w ww的盒子被插入到总重量为x xx的现有堆叠底部时该盒子承受的负载等于⌊ x w ⌋ \left\lfloor \frac{x}{w} \right\rfloor⌊wx​⌋。确定所有盒子可能承受的最小总负载。输入格式输入格式如下N A 1 A 2 … A N \begin{aligned} N \\ A_1 \ A_2 \ \ldots \ A_N \end{aligned}​NA1​A2​…AN​​2 ≤ N ≤ 200 000 2 \leq N \leq 200\,0002≤N≤2000001 ≤ A i ≤ 10 9 1 \leq A_i \leq 10^91≤Ai​≤109(1 ≤ i ≤ N 1 \leq i \leq N1≤i≤N)所有输入值均为整数。输出格式在一行中输出答案。输入输出样例 #1输入 #15 3 1 4 1 5输出 #13题意有N NN个 JAG Box。对于每个i 1 , 2 , … , N i 1, 2, \ldots, Ni1,2,…,N第i ii个盒子有一个整数重量A i A_iAi​。通过重复选择一个剩余的盒子并将其插入当前堆叠的最底部来建造一个垂直堆叠。当一个重量为w ww的盒子被插入到总重量为x xx的现有堆叠底部时该盒子承受的负载等于⌊ x w ⌋ \left\lfloor \frac{x}{w} \right\rfloor⌊wx​⌋。求所有盒子可能承受的最小总负载。思路考虑贪心做法只需按A i A_iAi​升序排序即可。采用邻项交换法证明设当前的堆叠总重量为x xx现有升序排序后两个数A i , A i 1 A_i,A_{i1}Ai​,Ai1​如果顺序放入则两数负载为⌊ x A i ⌋ ⌊ x A i A i 1 ⌋ \left\lfloor \frac{x}{A_i} \right\rfloor \left\lfloor \frac{x A_i}{A_{i1}} \right\rfloor⌊Ai​x​⌋⌊Ai1​xAi​​⌋如果交换顺序则两数负载为⌊ x A i 1 ⌋ ⌊ x A i 1 A i ⌋ \left\lfloor \frac{x}{A_{i1}} \right\rfloor \left\lfloor \frac{x A_{i1}}{A_i} \right\rfloor⌊Ai1​x​⌋⌊Ai​xAi1​​⌋。如果交换更优当且仅当⌊ x A i 1 ⌋ ⌊ x A i 1 A i ⌋ ≤ ⌊ x A i ⌋ ⌊ x A i A i 1 ⌋ \left\lfloor \frac{x}{A_{i1}} \right\rfloor \left\lfloor \frac{x A_{i1}}{A_i} \right\rfloor \le \left\lfloor \frac{x}{A_i} \right\rfloor \left\lfloor \frac{x A_i}{A_{i1}} \right\rfloor⌊Ai1​x​⌋⌊Ai​xAi1​​⌋≤⌊Ai​x​⌋⌊Ai1​xAi​​⌋变形为⌊ x A i A i 1 ⌋ − ⌊ x A i 1 ⌋ ≥ ⌊ x A i 1 A i ⌋ − ⌊ x A i ⌋ \left\lfloor \frac{x A_i}{A_{i1}} \right\rfloor - \left\lfloor \frac{x}{A_{i1}} \right\rfloor \ge \left\lfloor \frac{x A_{i1}}{A_i} \right\rfloor - \left\lfloor \frac{x}{A_i} \right\rfloor⌊Ai1​xAi​​⌋−⌊Ai1​x​⌋≥⌊Ai​xAi1​​⌋−⌊Ai​x​⌋分类讨论后可知在A i ≤ A i 1 A_i \le A_{i1}Ai​≤Ai1​时,及升序排序后⌊ x A i A i 1 ⌋ − ⌊ x A i 1 ⌋ ≤ 1 ≤ ⌊ x A i 1 A i ⌋ − ⌊ x A i ⌋ \left\lfloor \frac{x A_i}{A_{i1}} \right\rfloor - \left\lfloor \frac{x}{A_{i1}} \right\rfloor \le 1 \le \left\lfloor \frac{x A_{i1}}{A_i} \right\rfloor - \left\lfloor \frac{x}{A_i} \right\rfloor⌊Ai1​xAi​​⌋−⌊Ai1​x​⌋≤1≤⌊Ai​xAi1​​⌋−⌊Ai​x​⌋所以不交换更优。得出结论在A i ≤ A i 1 A_i \le A_{i1}Ai​≤Ai1​时不交换是更优的。代码#includebits/stdc.husingnamespacestd;#defineintlonglongintn,a[200001],ans,cnt;signedmain(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i)cina[i];sort(a1,a1n);//升序排序cnta[1];for(inti2;in;i)anscnt/a[i],cnta[i];//求负载coutans;return0;}