题目描述：有一个k(1≤k≤80)位的十进制正整数n，设计一个程序，找到满足条件:P3+ P2+3P≤n的P的最大值。
测试用例：
输入：
1000000000000001000000000000003000000000000001
输出：
100000000000000
复制代码
#include <iostream>
#include <string>
using namespace std;
#include "decnum.h"
decnum n,p;
int k;
char succ(char num)
{//后继数字
if (num=='9')
{
num = '0';
}
else
++num;
return num;
}
char pred(char num)
{//前一个数字
return --num;
}
bool IsOk(const char* temp,int size)
{//判断是否当前值符合条件
decnum num(temp,size);
decnum sum = pow(num, 3)+pow(num,2)+(num*3);
if (sum>n)
{//太大了
return false;
}
return true;
}
void search()
{
char* temp = new char[k];
int i;
//初始化都是0
for (i=0;i<k;++i)
{
temp[i] = '0';
}
temp[i] = '\0';
for (i=0;i<k;++i)
{
do
{
//尝试这一位
temp[i] = succ(temp[i]);
if (temp[i]=='0')
{//此位置从0到9都尝试过了
break;
}
}
while(IsOk(temp,k));
//回退到前一位合法值
temp[i] = pred(temp[i]);
}
//输出结果
p = decnum(temp,k);
cout<<p<<endl;
}
int main()
{
string line;
getline(cin,line);
n = decnum(line.c_str(), line.length());
k = line.length();//位数
search();
cout<<n<<endl;
return 0;
}
复制代码
本文转自Phinecos(洞庭散人)博客园博客，原文链接：http://www.cnblogs.com/phinecos/archive/2008/11/17/1335239.html，如需转载请自行联系原作者
