c - 给定 n，求加起来得到 n 的最大数

Question

oracle面试问的问题，比如我输入的是6，那么

• 5+1=6 回答:2
• 4+2=6 回答:2
• 3+2+1=6 答案:3

所以，最终答案应该是 3。(即需要 3,2,1 才能得到总和 6)

注意:不允许重复数字(即 1+1+1+1+1+1=6)

我用递归解决了，但面试官不满意。动态规划是否可行？

Answer 1

x个数的最小和是

所以只要找到满足不等式的x:

代码如下:

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);
    int x = 1;
    while ((x+1)*x/2 <= n) x++;
    x--; // now (x+1)*x/2 > n , so x is too large
    printf("%d\n", x);
    return 0;
}

如果 n 很大，您可以使用二分查找。