求证一个贪心
  • 板块学术版
  • 楼主_8762
  • 当前回复15
  • 已保存回复15
  • 发布时间2022/11/22 20:41
  • 上次更新2023/10/27 01:54:28
查看原帖
求证一个贪心
370829
_8762楼主2022/11/22 20:41

假设初始有n个点,m个物品

消除第i个点要求你现有物品不少于a[i],你的物品还会相应减少b[i] (b[i]<=a[i])

问当前m个物品是否能消除这n个点

贪心策略是将a[i]-b[i]从大到小排序依次消去

如果次策略不行 则不能消除

求证正确性

2022/11/22 20:41
加载中...