社区讨论

求问方法对错

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

讨论操作

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

当前回复
7 条
当前快照
1 份
快照标识符
@mik6ni5n
此快照首次捕获于
2025/11/29 19:03
3 个月前
此快照最后确认于
2025/11/30 20:00
3 个月前
查看原帖
考虑到 xi+yix_i+y_i 是连续买的基数值,有以下结论可证:
  • 至多存在一种糖果会买 >1>1 颗。
考虑反正法:假设有超过一种糖果买到第二颗,那不如将 xi+yix_i+y_i 更小的一种糖果多买。
于是将 xi+yix_i+y_i 排序,优先取最小的和连续买。
此时要考虑留下一些钱给其他的糖果购买第一颗
考虑特判,将第一颗糖果从小到大按价钱排序,如果连续两个第一颗糖果的价钱和超过了 minxi+yi\min{x_i+y_i},则必须留下这些钱购买。
最后一单颗要特判一下,做完了。

有个坑:当输出 83 的数据输出 82,说明你需要考虑一种情况:扔掉最后一颗价格最高的糖果,看能否换 minxi+yi\min{x_i+y_i} 的两颗糖果。

回复

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

正在加载回复...