社区讨论
求 NOIP T1 的贪心正确性以及对拍强度
学术版参与者 2已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @mil3y8yu
- 此快照首次捕获于
- 2025/11/30 10:35 3 个月前
- 此快照最后确认于
- 2025/12/02 14:25 3 个月前
想了一个贪心:先选出 最小的糖果,假设这个最小的 的值为 ,然后选出所有 小于等于 的糖果的 的和记作 ,然后将 用 一直减到 ,但是分别算两次,一次是 仍然大于等于 ,第二次是 被减到小于 ,再从小到大依次减去各个糖果的 值直到不能再减为止,两次取最大值)
考场上感觉是这样的,但是不会证明,一开始没有过掉样例#6,后来写了一个对拍,拿各种hack调了十几次(包括各种特判和各种情况的分类讨论),最后过掉了7个样例,并且结束的时候对拍了一万多次都AC(mt19937的随机数,毫秒时间戳)。
但是考完之后发现对拍的数据好像有点小:, 。
有没有大佬能看看我的贪心有没有伪,或者这个对拍强度一万次够不够稳过T1(看到有不少人卡#6)。
回复
共 3 条回复,欢迎继续交流。
正在加载回复...