I3
TTpandaS
·
·
算法·理论
命题
若整数 x,y,k 满足：
\left\lceil \dfrac{x}{k} \right\rceil+\left\lceil \dfrac{y}{k} \right\rceil < \left\lceil \dfrac{x+y+1}{k} \right\rceil
当且仅当
k \mid x, k \mid y
证明
定义
定义 r_1,r_2 表示 x,y 除以 k 的余数，即：
x \equiv r_1 \pmod {k}
y \equiv r_2 \pmod {k}
可以得到
x + y + 1 \equiv r_1+r_2+1 \pmod {k}
原定理等价于：
\left\lceil \dfrac{r_1}{k} \right\rceil+\left\lceil \dfrac{r_2}{k} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k} \right\rceil
由定义可得
r_1,r_2 \in [0,k)
r_1+r_2+1 \in [1,2k)
因此
1 \leq \left\lceil \dfrac{r1+r2+1}{k} \right\rceil \leq 2
分两种情况讨论。
-
\left\lceil \dfrac{r1+r2+1}{k} \right\rceil =1
此时若 \left\lceil \dfrac{r_1}{k} \right\rceil+\left\lceil \dfrac{r_2}{k} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k} \right\rceil，当且仅当 \left\lceil \dfrac{r_1}{k} \right\rceil = \left\lceil \dfrac{r_2}{k} \right\rceil = 0，即 r_1 = r_2 = 0，即
k \mid x, k \mid y
-
\left\lceil \dfrac{r1+r2+1}{k} \right\rceil = 2
此时若 \left\lceil \dfrac{r_1}{k} \right\rceil+\left\lceil \dfrac{r_2}{k} \right\rceil < \left\lceil \dfrac{r1+r2+1}{k} \right\rceil，即 \left\lceil \dfrac{r_1}{k} \right\rceil + \left\lceil \dfrac{r_2}{k} \right\rceil \leq 1，则总是满足 r_1=0 或 r_2=0。不失一般性的，设 r_1=0，则 r_1+r_2+1=r_2+1 \in [1,k] \leq k，因此 \left\lceil \dfrac{r1+r2+1}{k} \right\rceil = 1，与条件不符，因此此情况不可能发生。
总上，原定理成立。
应用
CF1237G Balanced Distribution *3500
1 分析
定义 1.1
定义一个函数 \text{Sum}(l,r,a) (l \leq r,l,r \in [1,n])，满足：
\text{Sum}(l,r,a)=\sum_{i=l}^{r}a_i
定义 1.2
定义每个位置的目标状态为 s，满足：
s=\dfrac{\text{Sum}(1,n,a)}{n}
定理 1.1
对于区间 [l,r]，若满足 \text{Sum}(l,r,a)=(r-l+1)\times s，则至多 \left\lceil \dfrac{r-l}{k-1} \right\rceil 次分配操作使得 \forall i \in [l,r],a_i=s 且其余数值不变。
证明 1.1
进行操作：
对于 \forall i \in [1,n] , a_i \to a_i-s。
此时原定理等价于：
对于区间 [l,r]，若满足 \text{Sum}(l,r,a)=0，则至多 \left\lceil \dfrac{r-l}{k-1} \right\rceil 次分配操作使得 \forall i \in [l,r],a_i=0 且其余数值不变。
定义 1.1.1
定义一个函数 f(l,r,x,a,t) 表示是否满足至多 t 次操作使得 a_l=x,\forall i \in [l+1,r],a_i=0 且其余数值不变。
特殊的，f(l,l,x,a,0)=[a_l=x]。
定理成立等价于若满足 f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1。
考虑任意情况下的 f(l,r,x,a,t)。
-
r-l+1 \leq k
f(l,r,x,a,t)=[x=\text{Sum}(l,r,a)][t \geq 1]
具体的，若满足 x=\text{Sum}(l,r,a)，则对 [l,l+k-1] 进行一次分配操作。
分配后的数值满足：
a_l=x
\forall i \in [l+1,r],a_i=0
区间 [r+1,l+k-1] 中的数不变。
-
\text{Sum}(l,l+k-1,a) \geq x
定义 1.1.2
定义一个数组 b，满足
b_l=x
\forall i \in [l+1,l+k-1),b_i=0
b_{l+k-1}=\text{Sum}(l,l+k-1,a)-x
\forall i \in [1,l)\wedge(l+k-1,n] ,b_i=a_i
f(l,r,x,a,t)=f(l+k-1,r,0,b,t-1)
具体的，先对 [l,l+k-1] 进行一次分配操作。
分配后的数值满足：
a_l=x
\forall i \in [l+1,l+k-1),a_i=0
a_{l+k-1}=\text{Sum}(l,l+k-1,a)-x
分配后的 a 数组即变成 b 数组。
此时再对后面的部分进行操作，等价于 f(l+k-1,r,0,b)。
-
\text{Sum}(l,l+k-1,a) < x
f(l,r,x,a,t)=f(l+k-1,r,a_{l+k-1}+x-\text{Sum}(l,l+k-1,a),a,t-1)
具体的，先对 [l+k-1,r] 进行分配操作。
分配后的数值满足：
a_{l+k-1}=a_{l+k-1}+x-\text{Sum}(l,l+k-1,a)
\forall i \in (l+k-1,r] , a_i=0
能否完成等价于 f(l+k-1,r,a_{l+k-1}+x-\text{Sum}(l,l+k-1,a),a,t-1)。
此时对 [l,l+k-1] 进行一次分配操作。
分配后的数值满足：
a_{l}=x
\forall i \in (l,l+k-1] , a_i=0
考虑待证命题 f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1。
通过上述 3 种情况对原问题进行归纳。
性质 1.1.1
对于情况 2,3 将 f(l,r,x,a,t) 归纳为 f(l',r',x',a',t') 时，满足 r'-l'=r-l-(k-1)。
性质 1.1.2
对于情况 2,3 将 f(l,r,x,a,t) 归纳为 f(l',r',x',a',t') 时，满足 \text{Sum}(l',r',a')=\text{Sum}(l',r',a)。
性质 1.1.3
对于情况 2,3 将 f(l,r,x,a,t) 归纳为 f(l',r',x',a',t') 时，满足 x'+\text{Sum}(l,r,a)-\text{Sum}(l',r',a)=x。
由性质 1.1.1 可得，在变成情况 1 前归纳次数不超过 \left\lceil \dfrac{r-l}{k-1} \right\rceil-1，因此在得到情况 1 时 [t \geq 1] 总是满足。
由性质 1.1.2，1.1.3 可得，由于初始状态 \text{Sum}(l,r,a)=x=0 ，每次归纳后得到的 f(l',r',x',a',t') 总是满足 \text{Sum}(l',r',a')=\text{Sum}(l',r',a)=x'+\text{Sum}(l,r,a)-x=x'，因此在得到情况 1 时 [x=\text{Sum}(l,r,a)] 总是满足。
总上，f(l,r,0,a,\left\lceil \dfrac{r-l}{k-1} \right\rceil)=1，原命题得证。
定理 1.2
对于相邻的两个区间 [l_1,r_1],[l_2,r_2] (1\leq l_1 \leq r_1 \le1 n,1 \leq l_2 \leq r_2 \leq n,l_2=r_1+1)，满足
\text{Sum}(l_1,r_1,a)=(r_1-l_1+1)\times s
\text{Sum}(l_2,r_2,a)=(r_2-l_2+1)\times s
，若分别操作的次数小于将两个区间合并为一个区间操作的次数，当且仅当两个区间的 \text{len}-1 为 k-1 的倍数。
形式化的，若满足
\left\lceil \dfrac{\text{len}_1-1}{k-1} \right\rceil+\left\lceil \dfrac{\text{len}_2-1}{k-1} \right\rceil < \left\lceil \dfrac{\text{len}_1+\text{len}_2-1}{k-1} \right\rceil
当且仅当
\text{len}_1-1 \equiv 0 \pmod {k-1}
\text{len}_2-1 \equiv 0 \pmod {k-1}
可以发现等价于本文所提的命题。
对原问题的分析
将原数组分为若干个区间 [l_i,r_i]，满足
\text{Sum}(l_i,r_i,a)=(r_i-l_i+1)\times s
答案为
\sum_{i} \left\lceil \dfrac{r_i-l_i}{k-1} \right\rceil
由定理 1.2 可得，可以一直合并区间直到满足
\text{len}-1 \equiv 0 \pmod {k-1}
此时答案为
\sum_{i} \dfrac{r_i-l_i}{k-1} = \dfrac{n}{k-1} - \sum_{i} \dfrac{1}{k-1}
因此答案与区间数量成负相关，贪心地尽可能多的划分区间即可。
具体的，对于 i，找到最大的 j 满足
j \leq i
\text{Sum}(j,i,a)=(i-j+1)\times s
i-j \equiv 0 \pmod {k-1}
则划分出区间 [i,j]。
证明 1.3
考虑反证。
设存在 p，满足
p < j \leq i
\text{Sum}(p,i,a)=(i-p+1)\times s
i-p \equiv 0 \pmod {k-1}
使得划分 [p,i] 更优。
则
\text{Sum}(p,j-1,a)=(j-1-p+1)\times s
j-1-p \equiv 0 \pmod {k-1}
此时可以划分出区间 [p,j-1]。
因此原方案中对于 [1,p-1] 和 [i+1,n] 部分采用与现方案相同的划分方式，而原方案中 [p,i] 可以划分为两个区间，现方案中只划分为了一个区间。与现方案比原方案更优的假设不符。
因此划分区间 [i,j] 最优。
2 实现
考虑如何实现上述贪心过程找到每个 i 匹配的端点 j。
进行操作：
对于 \forall i \in [1,n] , a_i \to a_i-s。
此时对于 i，满足条件的 j 可以刻画为
\text{Sum}(j,i,a)=0
i \equiv j \pmod {k-1}
条件一可以重新刻画为
\text{Sum}(1,j-1,a)=\text{Sum}(1,i,a)
因此维护二元组 (\text{Sum}(1,i,a),i \bmod k-1)，j 即为最大的下标，满足
j \leq i
(\text{Sum}(1,j-1,a),j \bmod k-1)=(\text{Sum}(1,i,a),i \bmod k-1)
使用 map 记录每个二元组最近一次出现的位置即可，时间复杂度 O(n \log n)。
由于原题中数组成环，最后枚举起点，可以实现 O(n^2) 的算法。
考虑倍增加速，计算 f_{i,j} 表示以 i 为起点划分 2^j 个区间的端点，可以将原算法改进为 O(n \log n)。
输出方案参照证明 1.1 中将问题化归的方式递归即可，时间复杂度 O(n)。
总时间复杂度 O(n \log n)。