| |
|
开发:
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。 输入格式 第一行包含两个整数 n,m。第二行包含 n 个整数 a1,a2,…,an。第三行包含 m 个整数 b1,b2,…,bm。 输出格式 一个整数,表示 k 的最大可能值。 数据范围 前三个测试点满足 1 ≤ n,m ≤ 10。 输入样例1: 7 6 输出样例1: 3 输入样例2: 3 3 输出样例2: 2 输入样例3: 1 4 输出样例3: 1 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() 函数优化读取数据和写入数据的速度:
使用 bufio.NewReader(),bufio.NewWriter() 与 fmt.Fscan() ,fmt.Fprintln() 方法优化输入输出,其中 bufio.NewReader() 函数中需要传递一个 io.Reader 类型的变量,只要是实现了? io.Reader 接口中的方法的类型就可以传递到函数中,一般可以传递标准输入和输出:os.Stdin,os,Stdout,文件句柄,代码提交上去明显比 fmt.Scan() 和 fmt.Println() 函数处理数据快很多,提交上去运行时间只需要几百毫秒:
python:
|
|
|
上一篇文章 下一篇文章 查看所有文章 |
|
开发:
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- |
|
网站联系: qq:121756557 email:121756557@qq.com IT数码 |