4380 合并石子（贪心）_石子合并问题贪心算法

1. 问题描述：

小 A 面前有 n 堆石子排成一排，每堆石子的数量从左到右依次为 a1，a2，…，an。小 B 面前有 m 堆石子排成一排，每堆石子的数量从左到右依次为 b1，b2，…，bm。
两人面前的石子总数相同，即 a1 + a2 + … + an = b1 + b2 + … + bm。每个人都可以对自己面前的石子堆进行任意次合并操作，两个人的操作次数可以不同。合并操作指将连续的若干堆相邻石子合并为一堆。请你确定一个最大的整数 k，满足：
小 A 停止所有操作后，面前恰好有 k 堆石子，每堆石子的数量从左到右依次为 a′1，a′2，…，a′k。
小 B 停止所有操作后，面前恰好有 k 堆石子，每堆石子的数量从左到右依次为 b′1，b′2，…，b′k。
对于 1 ≤ i ≤ k，a′i = b′i 均成立。输出这个 k 的最大可能值。

输入格式

第一行包含两个整数 n，m。第二行包含 n 个整数 a1，a2，…，an。第三行包含 m 个整数 b1，b2，…，bm。

输出格式

一个整数，表示 k 的最大可能值。

数据范围

前三个测试点满足 1 ≤ n，m ≤ 10。
所有测试点满足 1 ≤ n，m ≤ 10 ^ 5，1 ≤ ai，bi ≤ 10 ^ 6，a1 + a2 + … + an = b1 + b2 +…+ bm ≤ 10 ^ 6；

输入样例1：

7 6
2 5 3 1 11 4 4
7 8 2 4 1 8

输出样例1：

3

输入样例2：

3 3
1 10 100
1 100 10

输出样例2：

2

输入样例3：

1 4
4
1 1 1 1

输出样例3：

1
来源：https://www.acwing.com/problem/content/description/4383/

2. 思路分析：

分析题目可以知道已知两个数轴，我们需要将两个数轴都分成 k 段，这两个数轴 k 段中对应的每一段的和都是相等的，由于 a1 + a2 + … + an = b1 + b2 + … + bm，最少可以分为一段，所以题目肯定是有解的，由下图可知，我们找到第一个数轴与第二个数轴当前和相等的一段的位置，分别记为 i 和 j，这个时候可以分为两种情况，最优解包括位置 i 和 j 分界点与不包括 i 和 j 分界点，如果包含 i 和 j 分界点，那么如果后面找到下一段相等的分界点分别为 i' 和 j'，此时 i 和 i' 与 j 和 j' 之间的和是相等的，所以当包含 i 和 j 分界点的时候那么分解的段数是更多的，也即当找到相等一段的时候包含 i 和 j 分界点的时候那么结果会更优，所以当我们找到两个数轴相等的一段的时候分界点就需要包含到最优解中，分解的段数加 1；如何找到两个数轴中相等的一段呢？可以发现我们可以使用双指针来解决（两个指针是单调的，当一个指针往右走的时候那么另外一个指针也是单调往右走的）：

3. 代码如下：

go：使用 fmt.Scan() 和 fmt.Println() 函数处理输入输出的速度是比较慢的，当数据量超过 10 ^ 5 之后读取输入数据和输出数据会变得很慢，下面使用 fmt.Scan() 和 fmt.Println() 函数运行时间比 python 还慢，如果代码中的时间复杂度再高一点肯定就会超时（TLE），这个时候就需要使用 bufio.NewRead() 函数优化读取数据和写入数据的速度：

package main
 
import "fmt"
 
func main() {
	var (
		n, m int
	)
	fmt.Scan(&n, &m)
	a := make([]int, n+10)
	b := make([]int, m+10)
	s1 := make([]int, n+10)
	s2 := make([]int, m+10)
	for i := 1; i <= n; i++ {
		fmt.Scan(&a[i-1])
		s1[i] += s1[i-1] + a[i-1]
	}
	for i := 1; i <= m; i++ {
		fmt.Scan(&b[i-1])
		s2[i] += s2[i-1] + b[i-1]
	}
	res := 0
	j := 1
	for i := 1; i <= n; i++ {
		for {
			if s2[j] >= s1[i] {
				break
			}
			j += 1
		}
		if s1[i] == s2[j] {
			res += 1
		}
	}
	fmt.Print(res)
}

使用 bufio.NewReader()，bufio.NewWriter() 与 fmt.Fscan() ，fmt.Fprintln() 方法优化输入输出，其中 bufio.NewReader() 函数中需要传递一个 io.Reader 类型的变量，只要是实现了  io.Reader 接口中的方法的类型就可以传递到函数中，一般可以传递标准输入和输出：os.Stdin，os,Stdout，文件句柄，代码提交上去明显比 fmt.Scan() 和 fmt.Println() 函数处理数据快很多，提交上去运行时间只需要几百毫秒：

package main
 
import (
	"bufio"
	"fmt"
	"io"
	"os"
)
 
func run(r io.Reader, w io.Writer) {
	in := bufio.NewReader(r)
	out := bufio.NewWriter(w)
	defer out.Flush()
	var (
		n, m int
	)
	fmt.Fscan(in, &n, &m)
	a := make([]int, n+10)
	b := make([]int, m+10)
	s1 := make([]int, n+10)
	s2 := make([]int, m+10)
	for i := 1; i <= n; i++ {
		fmt.Fscan(in, &a[i-1])
		s1[i] += s1[i-1] + a[i-1]
	}
	for i := 1; i <= m; i++ {
		fmt.Fscan(in, &b[i-1])
		s2[i] += s2[i-1] + b[i-1]
	}
	res := 0
	j := 1
	for i := 1; i <= n; i++ {
		for {
			if s2[j] >= s1[i] {
				break
			}
			j += 1
		}
		if s1[i] == s2[j] {
			res += 1
		}
	}
	fmt.Fprintln(out, res)
}
 
func main() {
	run(os.Stdin, os.Stdout)
}

python：

class Solution:
    def process(self):
        n, m = map(int, input().split())
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        s1, s2 = [0] * (n + 10), [0] * (m + 10)
        # 计算前缀和
        for i in range(1, n + 1):
            s1[i] += s1[i - 1] + a[i - 1]
        for i in range(1, m + 1):
            s2[i] += s2[i - 1] + b[i - 1]
        res = 0
        j = 1
        for i in range(1, n + 1):
            # 通过双指针找到当前相等的位置
            while s2[j] < s1[i]: j += 1
            if s1[i] == s2[j]:
                res += 1
        return res
 
 
if __name__ == "__main__":
    print(Solution().process())