社区讨论

求 NOIP T1 的贪心正确性以及对拍强度

学术版参与者 2已保存回复 3

讨论操作

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

当前回复
3 条
当前快照
1 份
快照标识符
@mil3y8yu
此快照首次捕获于
2025/11/30 10:35
3 个月前
此快照最后确认于
2025/12/02 14:25
3 个月前
查看原帖
想了一个贪心:先选出 x+yx+y 最小的糖果,假设这个最小的 x+yx+y 的值为 minsumminsum,然后选出所有 xix_i 小于等于 minsum/2minsum/2 的糖果的 xx 的和记作 sumxsumx,然后将 mmminsumminsum 一直减到 sumxsumx,但是分别算两次,一次是 mm 仍然大于等于 sumxsumx,第二次是 mm 被减到小于 sumxsumx,再从小到大依次减去各个糖果的 xx 值直到不能再减为止,两次取最大值)
考场上感觉是这样的,但是不会证明,一开始没有过掉样例#6,后来写了一个对拍,拿各种hack调了十几次(包括各种特判和各种情况的分类讨论),最后过掉了7个样例,并且结束的时候对拍了一万多次都AC(mt19937的随机数,毫秒时间戳)。
但是考完之后发现对拍的数据好像有点小:n<=5n<=5, m<=20m<=20
有没有大佬能看看我的贪心有没有伪,或者这个对拍强度一万次够不够稳过T1(看到有不少人卡#6)。

回复

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

正在加载回复...