竞赛
考级
题意分析 给出一个整数nnn,要求找到一个数字xxx,计算所有小于nnn的xxx的倍数之和SSS。 xxx的取值有许多,找到其中SSS数值最大的xxx输出即可。 算法分析 对于所有的情况来说,当x=2x=2x=2的时候SSS的取值一定为最大,所以直接输出222一定为最优解。 但是有一种特殊情况,为n=3n=3n=3时,此时x=3x=3x=3比x=2x=2x=2更优,因此需要特殊判断下即可。 时间复杂度分析 O(1)O(1)O(1) STD标程
最简版
∵S=k(k+1)x2,kx≤n\because S=\dfrac{k(k+1)x}{2},kx\le n∵S=2k(k+1)x ,kx≤n ∴Smax=n(k+1)2\therefore S_{max}=\dfrac{n(k+1)}{2}∴Smax =2n(k+1) 所以kkk越大,即xxx越小SSS越大. 注意判断123特殊情况 时间复杂度:O(1)O(1)O(1)
提交答案之后,这里将显示提交结果~