技巧
前缀和 二分
思路
构建前缀和 二分搜索前缀和找到第一个>=t的位置
实现
package main import ( "bufio" . "fmt" "io" "os" ) // https://ac.nowcoder.com/acm/problem/24866 func NC24866(_r io.Reader, _w io.Writer) { in, out := bufio.NewReader(_r), bufio.NewWriter(_w) defer out.Flush() var N, Q int Fscan(in, &N, &Q) sumArr := make([]int, N + 1) // 前缀和 for i := 1; i <= N; i++{ Fscan(in, &sumArr[i]) sumArr[i] += sumArr[i-1] } for ;Q > 0; Q--{ var t int Fscan(in, &t) l, r := 0, N for l <= r { mid := l + (r-l) / 2 if sumArr[mid] <= t { l = mid + 1 }else { r = mid - 1 } } Fprintln(out, r + 1) } } func main() { NC24866(os.Stdin, os.Stdout) }