hdu 5646 ||bc #76 div 2 (贪心)

题目链接

题意:将正整数n(n<=1E9),拆分成k个(k<=1E9)个互不相等的正整数,并且使得k个正整数的乘积最大。如果可以拆分,输出最大乘积,否则输出-1.

思路:其实是道贪心。。容易知道,k个互不相同的正整数的最小的和为sum=(k+1)*k/2,以此来判断是否有解。如果有解。那么找到最大的i,使得从i 开始的连续k个正整数相加的和小于等于n.

由于k不会超过1E5(否则一定无解),所以可以开个数组存一下拆分的每个数。

然后设此时还需要添加r才能到n,那么贪心得想,一定是给最大的r个每个增加1最后的乘积会最大。这等效于直接将第k-r+1个直接增加r.

注意全程long long

以及:

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

开了同步以后scanf/puts/printf  和 cin/cout 后会导致WA!!!

原因是puts也是<stdio.h>里的。。

c和c++各有一套指针。。随时同步,所以cin会慢。。关掉同步会快,但是由于已经关掉同步了,混用就会有问题。 以前不知道puts也是不能混用的QAQ

 

 

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz