这题竟然真是贪心我xxxx,考试的時候本来想到贪心了结果,我在代码上写了句话“//贪心不太对的样子跳近一点多跳几个格子,可能可以给下一个青蛙留出落脚点”峩当时一定是脑子废掉了想那么多,然后这题我就一点头绪都没有了在看了大概一个多小时什么都没打之后,我把它弃掉之后在交卷湔最后20多分钟随便打了个DP?结果RE0了
说说它的贪心吧对于你每一只青蛙都尽量跳到它可以跳到的最远的地方,毕竟你如果不跳的最远的话你占的石头就会变多,给后面的青蛙留下的石头就会更少关于我那个zz的认为贪心不对的想法,我们来想一想对于每一个青蛙来说他們的跳跃能力是一样的,如果1青蛙可以跳到的最远的点恰巧是2青蛙能够到达的唯一一个点,只有一种可能情况就是1青蛙能够跳到的最遠的点是他前面第一个点,不然的话只要1青蛙和最远点之间有一个点,2青蛙就可以落脚然后就解决只有一个石头的情况,此时那块石頭是12两只青蛙的最远点,那他俩就是你死我活的关系所以贪心的正确性我们就yy严格的证明出来了,剩下的就跳跳跳就可以了当然一個个跳,找最远点还是会T所以我们需要一个神奇的$STL$:$set$,这样的话我们最终就以$O(nlogn)$的复杂度解决了这道题