第三题样例很少,很多100%的其实不对。比如1 2 5 这个其实只需要2次,但是看评论的一些方法需要3次。我的思路是,找出最大元素,和次大元素,先把最大元素/2,直到“将”要比次大元素小。在把第一个元素*2直到比次大元素大。再看下此时和最大元素比还需不需要再乘一次2。这个正确性证明:如果此时想让第一个元素少乘一次2,就要让最大和次大都要/2,所以肯定步数会变多。而对于最大元素,其除2向下取整比第一个元素*2要小的多一些,肯定贪心希望最大元素尽量除2(比如1,2,5这种5/2=1肯定比2*2划算)。
2 5

相关推荐

牛客网
牛客企业服务