题目链接
本题目的题解中提到了一个贪心策略:对于大小未知的正整数集合LLL,和给定的正整数mmm,mmm满足m∗(m+1)/4m*(m+1)/4m∗(m+1)/4为整数,要求其满足两个方程:
∑i∣L∣li=m\sum_{i}^{|L|}l_{i}=m∑i∣L∣li=m
∑i∣L∣li∗(li−1)/2=m∗(m+1)/4\sum_{i}^{|L|}l_{i}*(l_{i}-1)/2=m*(m+1)/4∑i∣L∣li∗(li−1)/2=m∗(m+1)/4
题解中给出的贪心策略为从大到小尽可能取大的lil_ili,就可以得出一个构造方式。
求问为什么这样的方法一定能构造出一个合法的解。