背景:
原题链接
现在的五级越来越水了,都简单成什么样了。2025年及以前的五级还是有点难度的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
思路:
> 获得自己以及左侧所有小朋友的手上数字之和个糖果,所以要让大的数放前面,将数组aaa从大到小排序,然后遍历111 ~ nnn遍历,再每次加111 ~ iii的糖果数,最后输出。
> 本题也可以用前缀和优化,时间复杂度O(n)O(n)O(n),但由于1≤n≤10001\leq n \leq 10001≤n≤1000,所以原代码时间复杂度O(n2)O(n^2)O(n2),不会超时,不优化也可以。然而本题不知道是数据水还是什么,运行时间没什么区别。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
代码:
时间复杂度O(n2)O(n^2)O(n2)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
前缀和优化代码:
时间复杂度O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
结语:
希望对大家学习OI有帮助!