求助贪心策略证明
  • 板块学术版
  • 楼主哈撒各一
  • 当前回复1
  • 已保存回复1
  • 发布时间2023/9/13 22:20
  • 上次更新2023/11/2 21:00:22
查看原帖
求助贪心策略证明
226447
哈撒各一楼主2023/9/13 22:20

题目链接

本题目的题解中提到了一个贪心策略:对于大小未知的正整数集合LL,和给定的正整数mm,mm满足m∗(m+1)/4m*(m+1)/4为整数,要求其满足两个方程:

∑i∣L∣li=m\sum_{i}^{|L|}l_{i}=m

∑i∣L∣li∗(li−1)/2=m∗(m+1)/4\sum_{i}^{|L|}l_{i}*(l_{i}-1)/2=m*(m+1)/4

题解中给出的贪心策略为从大到小尽可能取大的lil_i,就可以得出一个构造方式。

求问为什么这样的方法一定能构造出一个合法的解。

2023/9/13 22:20
加载中...