关于单调性证明
查看原帖
关于单调性证明
239241
Singercoder楼主2021/5/26 22:01

自己随便口胡的,不是很严谨

比较两种情况1和2,设它们的自动提交行数分别为 n1n2n_1 \le n_2 ,令 ix,yi_{x,y} 表示情况x迎来第y次提交的时间

考虑它们各自迎来第1次提交的时间 i1,1i_{1,1}i2,1i_{2,1} ,显然有 i1,1i2,1i_{1,1} \le i_{2,1}

则当情况1的时间达到 i2,1i_{2,1} 时,提交题数和当前行数都大于等于情况2的,因此有 i1,2i2,2i_{1,2} \le i_{2,2}

归纳可知 i1,yi2,yi_{1,y} \le i_{2,y},于是就有 k1k2k_1 \ge k_2

2021/5/26 22:01
加载中...