社区讨论

反悔贪心做法是否可行

P14635[NOIP2025] 糖果店参与者 8已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mika83cq
此快照首次捕获于
2025/11/29 20:43
3 个月前
此快照最后确认于
2025/12/01 09:25
3 个月前
查看原帖
考场上想到了下面三个性质:
  • 除了 x+yx+y 最小的一组之外,都不可能选两个以上。
  • mid=(xmin+ymin)/2mid=(x_{min}+y_{min})/2x>=midx>=mid 最多选一个。
于是就先选所有 <mid<midxx,然后全选 x+yx+y 最小的,余数选没选的当中 xx 最小的。
或者考虑撤销开始时选的 xx 当中最大的那一个,再跟上面的一样操作,取较大值为答案。
原因是显然撤销一个以上是不优的。过了所有大样例和几个小时的对拍。求各位巨佬看看是否可过。

回复

7 条回复,欢迎继续交流。

正在加载回复...