Nirvana【思维+暴力优化】 |
您所在的位置:网站首页 › nirvana主题破解版 › Nirvana【思维+暴力优化】 |
Nirvana
题目链接(点击) Kurt reaches nirvana when he finds the product of all the digits of some positive integer. Greater value of the product makes the nirvana deeper. Help Kurt find the maximum possible product of digits among all integers from 11 to nn. Input The only input line contains the integer nn (1≤n≤2⋅1091≤n≤2⋅109). Output Print the maximum product of digits among all integers from 11 to nn. Examples Input 390Output 216Input 7Output 7Input 1000000000Output 387420489Note In the first example the maximum product is achieved for 389389 (the product of digits is 3⋅8⋅9=2163⋅8⋅9=216). In the second example the maximum product is achieved for 77 (the product of digits is 77). In the third example the maximum product is achieved for 999999999999999999 (the product of digits is 99=38742048999=387420489). 题意:给出一个小于2e9的正整数n 要求找到从1~n 中的一个数 满足它的每位数相乘结果最大 并输出该结果 思路:开始肯定是想直接暴力 从1~n 但明显会超时 对于每个输入的数n 例如:390 先考虑把他-1 变成389 然后再-1 变成388 、387 仔细想想根本不需要减那么多次 因为389 各位相乘肯定大于 388 同理4099 先-100 变成3999 再-100变成3899 也没必要 所以总结规律如下: 从数n的最后一位开始 通过向前一位借1的方法 每次都把最后一位变成9 (最大值对应的数肯定会出现在这些情况里面) 例如: 390 --> 389 --> 299 --> 99 (99可以不考虑,因为前面的299 肯定大于 199) 最后把每一种情况对应的值都计算出来 取最大的 AC代码: #include typedef long long LL; LL sum(LL n) { LL num=n,count2=0; char a[15]; while(num){ LL num1=num%10; num/=10; a[count2++]=num1+'0'; } LL sum2=1; for(int i=count2-1;i>=0;i--){ sum2=sum2*(a[i]-'0'); } return sum2; } int main() { LL c[15]={0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,10000000000}; LL n; scanf("%lld",&n); LL maxx=sum(n),j=1; while(n>=0){ while((n/c[j])%10!=9&&n>=0){ n-=c[j]; } LL num2=sum(n); if(num2>maxx){ maxx=num2; } j++; } printf("%lld\n",maxx); return 0; }
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |