问题分析与核心思路
问题本质拆解
这是一个典型的区间更新+单点查询问题,需要高效处理p次区间加分操作,最后找出全班最低分。
关键观察
时间复杂度要求:n和p最大为10⁴,暴力解法O(pn)会导致10⁸次操作,接近时间限制边缘
差分算法优势:可以将区间更新操作降为O(1),最后通过前缀和计算得到最终分数,总时间复杂度O(n+p)
数据范围:初始分数≤100,每次加分≤100,最多10⁴次操作,最终分数≤100+10⁴100=1,001,000,使用int完全足够
最低分查找:可以在计算最终分数的同时直接找出最小值,不需要额外遍历
代码详细解释
差分算法原理
核心思想:将区间更新转换为单点更新,通过前缀和得到最终结果 对区间[x,y]加z,等价于:
diff[x] += z 表示从x开始,所有元素都加z
diff[y+1] -= z 表示从y+1开始,抵消前面的加z操作