求一个贪心正确性证明QAQ

P1233 木棍加工

不知道你是怎么贪心的,,不过我给你说一下我的。 我把长和宽按长为优先排了一下序 ```c bool cmp(node xx,node yy) { if(xx.x!=yy.x) return xx.x>yy.x; return xx.y>yy.y; } ``` 就酱,你应该可以看懂,.x是长,.y是宽 因为如果一个木棍特别长的话,就算它的宽特别短,也没有别的木棍可以使它不用准备时间,(当然你也可以以宽为优先,一样滴啦) 然后嘞,我是从排好序的序列一遍一遍的扫,只要下一个木棒可以不用准备时间就把它加进来,然后记录下来。扫到尾之后再扫一遍,,,,,直到把所有木棍都记录后,算法结束
by 幽梦蓝殇 @ 2018-11-05 19:52:55


至于这样做为什么是对的, 我这样跟你说,每一个木棍的存在都有着它对整个序列的影响,我们希望木棍越少越好, 打比方中间有一个木棍,如果选了它后,之后的木棍还可以随便接,那么选它何乐而不为呢,比起不选它少了一个木棍而且对后面没有影响, 如果选了它后,之后本来能接的木棍不能接了,那么因为这个木棍在前面,它的影响值很大,不选他的话虽然能短时间内多几个消耗木棍,但是这个影响值很大的木棍就没有办法搞掉了,甚至它一个木棍就会耗掉一次准备机会,
by 幽梦蓝殇 @ 2018-11-05 20:08:59


不知道这样说你能不能明白,希望能帮到你,
by 幽梦蓝殇 @ 2018-11-05 20:10:27


|