[R60B] 均摊

数据规模：$1 \le n, x, a_i \le 100$。

思路

条件 $\frac{a_1 + \dots + a_y}{y} \ge x$ 等价于前缀和 $s_y \ge x \times y$。枚举 $y = 1 \sim n$，边累加前缀和边判断：第一个满足的 $y$ 是答案的最小值，每遇到一个满足的 $y$ 都更新答案的最大值。题目保证至少存在一个满足条件的 $y$。

复杂度：时间 $O(n)$，空间 $O(n)$。

仓颉实现

import std.env.*
import std.convert.*

main(): Int64 {
    let reader = getStdIn()
    let nx = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p => Int64.parse(p) })
    let n = nx[0]
    let x = nx[1]
    let a = reader.readln().getOrThrow().split(" ", removeEmpty: true).map({ p => Int64.parse(p) })
    var sum: Int64 = 0
    var mn: Int64 = -1
    var mx: Int64 = -1
    for (y in 1..(n + 1)) {
        sum = sum + a[y - 1]
        if (sum >= x * y) {
            if (mn < 0) {
                mn = y
            }
            mx = y
        }
    }
    let out = StringBuilder()
    out.append(mn)
    out.append(" ")
    out.append(mx)
    println(out.toString())
    return 0
}

要点：

• 判断条件写成 $s_y \ge xy$ 可避免浮点除法。
• 最小值只在第一次满足时记录（用 mn < 0 判断是否已记录），最大值每次满足都更新。