专栏文章

Proof of CF2013D

wwuxigk
个人记录参与者 1已保存评论 0

文章操作

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

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

Some notation

For an array AA of length nn:
  • min⁡(A)=min⁡i=1nAi\min(A)=\min_{i=1}^nA_i
  • max⁡(A)=max⁡i=1nAi\max(A)=\max_{i=1}^nA_i
  • L(A,i)=1i∑k=1iAkL(A,i)=\frac{1}{i}\sum_{k=1}^iA_k
  • L(A)=min⁡i=1nL(A,i)L(A)=\min_{i=1}^nL(A,i)
  • R(A,i)=1n−i+1∑k=inAkR(A,i)=\frac{1}{n-i+1}\sum_{k=i}^nA_k
  • R(A)=max⁡i=1nR(A,i)R(A)=\max_{i=1}^nR(A,i)
  • An operation on position ii is called "balancing" iff Ai>Ai+1A_i>A_{i+1}.

Lemma 1

If AA turns into BB after some operations, there must be min⁡(B)≤⌊L(A)⌋\min(B)\le\lfloor L(A)\rfloor and max⁡(B)≥⌈R(A)⌉\max(B)\ge\lceil R(A)\rceil.

Proof of Lemma 1

Assume that min⁡(B)>⌊L(A)⌋\min(B)>\lfloor L(A)\rfloor. Let ii be some index satisfying L(A,i)=L(A)L(A,i)=L(A). Notice that L(B,i)≥min⁡(B)L(B,i)\ge\min(B), so we have: ⌊L(B,i)⌋≥⌊min⁡(B)⌋=min⁡(B)>⌊L(A)⌋=⌊L(A,i)⌋\lfloor L(B,i)\rfloor\ge\lfloor\min(B)\rfloor=\min(B)>\lfloor L(A)\rfloor=\lfloor L(A,i)\rfloor
So L(B,i)>L(A,i)L(B,i)>L(A,i), i.e. ∑k=1iBk>∑k=1iAk\sum_{k=1}^iB_k>\sum_{k=1}^iA_k.
However, ∀j≠i\forall j\ne i, operations on position jj does not affect ∑k=1iBk\sum_{k=1}^iB_k, and operations on position ii makes ∑k=1iBk\sum_{k=1}^iB_k smaller, so there must be ∑k=1iBk≤∑k=1iAk\sum_{k=1}^iB_k\le\sum_{k=1}^iA_k. Contradiction!
Similarly, we can prove that max⁡(B)≥⌈R(A)⌉\max(B)\ge\lceil R(A)\rceil.

Lemma 2

If AA turns into BB after a balancing operation, there must be ⌊L(A)⌋=⌊L(B)⌋\lfloor L(A)\rfloor=\lfloor L(B)\rfloor and ⌈R(A)⌉=⌈R(B)⌉\lceil R(A)\rceil=\lceil R(B)\rceil.

Proof of Lemma 2

Suppose that the balancing operation is performed on position ii. Notice that ∀j≠i,L(A,j)=L(B,j)\forall j\ne i,L(A,j)=L(B,j) and L(B,i)=L(A,i)−1i<L(A,i)L(B,i)=L(A,i)-\frac{1}{i}<L(A,i), so L(B)≤L(A)L(B)\le L(A), so ⌊L(B)⌋≤⌊L(A)⌋\lfloor L(B)\rfloor\le\lfloor L(A)\rfloor.
Assume ⌊L(B)⌋<⌊L(A)⌋\lfloor L(B)\rfloor<\lfloor L(A)\rfloor, then ∀j≠i,⌊L(B,i)⌋<⌊L(B,j)⌋\forall j\ne i,\lfloor L(B,i)\rfloor<\lfloor L(B,j)\rfloor. (Otherwise ∃j≠i,⌊L(B)⌋=⌊L(B,j)⌋=⌊L(A,j)⌋≥⌊L(A)⌋\exists j\ne i,\lfloor L(B)\rfloor=\lfloor L(B,j)\rfloor=\lfloor L(A,j)\rfloor\ge\lfloor L(A)\rfloor)
If i=1i=1, we have ⌊L(B,1)⌋<⌊L(B,2)⌋\lfloor L(B,1)\rfloor<\lfloor L(B,2)\rfloor, i.e. A1−1<⌊A1+A22⌋A_1-1<\left\lfloor\frac{A_1+A_2}{2}\right\rfloor. Discuss the value of A2A_2: if A2≤A1−2A_2\le A_1-2, then ⌊A1+A22⌋≤A1−1\left\lfloor\frac{A_1+A_2}{2}\right\rfloor\le A_1-1, leading to contradiction; if A2=A1−1A_2=A_1-1, then ⌊A1+A22⌋=A1−1\left\lfloor\frac{A_1+A_2}{2}\right\rfloor= A_1-1, also leading to contradiction.
If i>1i>1, on one hand we have ⌊L(B,i)⌋<⌊L(B,i−1)⌋\lfloor L(B,i)\rfloor<\lfloor L(B,i-1)\rfloor, so L(B,i)<L(B,i−1)L(B,i)<L(B,i-1), after simplification we have ∑k=1i−1Ak>(i−1)(Ai−1)\sum_{k=1}^{i-1}A_k>(i-1)(A_i-1)
On the other hand, we can calculate the difference between L(B,i)L(B,i) and L(B,i+1)L(B,i+1) using Ai+1≤Ai−1A_{i+1}\le A_i-1 and the previous inequality, after simplification we have L(B,i)−L(B,i+1)>−1i+1L(B,i)-L(B,i+1)>-\frac{1}{i+1}
Decompose the difference into integral part and fractional part, we have {L(B,i)}>⌊L(B,i+1)⌋−⌊L(B,i)⌋−1i+1+{L(B,i+1)}\lbrace L(B,i)\rbrace>\lfloor L(B,i+1)\rfloor-\lfloor L(B,i)\rfloor-\frac{1}{i+1}+\lbrace L(B,i+1)\rbrace
Because ⌊L(B,i+1)⌋−⌊L(B,i)⌋≥1\lfloor L(B,i+1)\rfloor-\lfloor L(B,i)\rfloor\ge 1 and {L(B,i+1)}≥0\lbrace L(B,i+1)\rbrace\ge 0, we have {L(B,i)}>ii+1\lbrace L(B,i)\rbrace>\frac{i}{i+1}. However, since L(B,i)L(B,i) can be expressed as a rational number with denominator ii, so {L(B,i)}≤i−1i\lbrace L(B,i)\rbrace\le\frac{i-1}{i}, leading to contradiction.
In summary, there must be ⌊L(A)⌋=⌊L(B)⌋\lfloor L(A)\rfloor=\lfloor L(B)\rfloor. Similarly, we can prove that ⌈R(A)⌉=⌈R(B)⌉\lceil R(A)\rceil=\lceil R(B)\rceil.

Construction and proof of the answer

For an array AA of length nn, perform balancing operations to it continuously until you get a monotonically non-decreasing array BB. Since BB is monotonically non-decreasing, there must be min⁡(B)=B1=L(B)=⌊L(B)⌋\min(B)=B_1=L(B)=\lfloor L(B)\rfloor and max⁡(B)=Bn=R(B)=⌈R(B)⌉\max(B)=B_n=R(B)=\lceil R(B)\rceil. By Lemma 2 we have ⌊L(B)⌋=⌊L(A)⌋\lfloor L(B)\rfloor=\lfloor L(A)\rfloor and ⌈R(B)⌉=⌈R(A)⌉\lceil R(B)\rceil=\lceil R(A)\rceil, so max⁡(B)−min⁡(B)=⌈R(A)⌉−⌊L(A)⌋\max(B)-\min(B)=\lceil R(A)\rceil-\lfloor L(A)\rfloor.
According to Lemma 1, no matter what operations are performed on AA, the final array CC must satisfy max⁡(C)−min⁡(C)≥⌈R(A)⌉−⌊L(A)⌋\max(C)-\min(C)\ge\lceil R(A)\rceil-\lfloor L(A)\rfloor, so ⌈R(A)⌉−⌊L(A)⌋\lceil R(A)\rceil-\lfloor L(A)\rfloor is the answer.

评论

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

正在加载评论...