问题分析

我们需要找到不超过给定整数$M$的最大数，该数可以表示为立方数（$a^3$）和四面体数（$\frac{b(b+1)(b+2)}{6}$）的和。即：

$\text{maximize } (a^3 + T_b) \leq M$

其中：

• $a^3$ 是立方数，$a \geq 0$。

• $T_b = \frac{b(b+1)(b+2)}{6}$ 是四面体数，$b \geq 0$。

解决思路

1. 预处理四面体数： • 由于$M \leq 151200$，我们可以预先计算所有可能的四面体数$T_b$，直到$T_b \leq 151200$。

   • 四面体数的计算公式为$T_b = \frac{b(b+1)(b+2)}{6}$，我们可以通过循环计算$T_b$，直到$T_b$超过$151200$。

2. 枚举立方数和四面体数的组合： • 对于每个输入$M$，我们需要枚举所有可能的立方数$a^3 \leq M$，然后对于每个$a^3$，检查是否存在四面体数$T_b$使得$a^3 + T_b \leq M$。

   • 对于每个$a$，我们可以计算剩余值$M - a^3$，然后在预处理的四面体数列表中找到不超过该剩余值的最大四面体数$T_b$。

3. 优化枚举范围： • 立方数$a^3$的枚举范围是$a \leq \lfloor M^{1/3} \rfloor$。

   • 四面体数$T_b$的枚举范围可以通过预处理确定，确保$T_b \leq M - a^3$。

4. 查找最大和： • 对于每个$a$，找到最大的$T_b$满足$T_b \leq M - a^3$，然后计算$a^3 + T_b$。

   • 最终结果是所有可能的$a^3 + T_b$中的最大值。

代码实现

#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<memory.h>
using namespace std;
int main()
{
    int n,i,j,x;
    int ans;
    while(~scanf("%d",&n))
    {
        if(n==0)
            break;
        ans=0;
        for(i=0;i*i*i<=n;i++)
        {
            for(j=0;j*(j+1)*(j+2)/6<=n;j++)
            {
                x=i*i*i+j*(j+1)*(j+2)/6;
                if(x<=n)
                {
                    ans=max(ans,x);
                }
                else
                {
                    break;
                }
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}