技巧
前缀和 二分
思路
构建前缀和 二分搜索前缀和找到第一个>=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)
}

京公网安备 11010502036488号