IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 4380 合并石子(贪心) -> 正文阅读

[数据结构与算法]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())
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-06-08 19:12:49  更:2022-06-08 19:13:03 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 2:03:44-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码