算法刷题day25:多路归并

news/2024/4/24 16:39:32/文章来源:https://blog.csdn.net/weixin_60033897/article/details/136566621

目录

  • 引言
  • 概念
  • 一、鱼塘钓鱼
  • 二、技能升级
  • 三、序列

引言

关于这个多路并归蓝桥杯考的不是很多,如果要出的话,可能模型都会差不多,因为不会出太难的题,难题基本上都是贪心、DP之类的,所以好好刷题刷熟练就行了,见过熟悉即可,加油!


概念

多路归并:首先可以参考博客算法刷题:归并排序、归并排序,这个多路归并其实就是一种类型的题目,还是要因题而异。


一、鱼塘钓鱼

标签:多路归并

思路: 1. 1. 1. 首先核心就是则个人钓鱼不会折返跑,因为每个鱼塘钓的鱼的数量是和你钓的次数有关,和时间无关,如果你又折返跑回来钓的话,还不如就直接在上一次的鱼塘多钓几次,还浪费路上的时间,所以最优解肯定是一条直线,而不会是来回的跑,因为这个 N N N 比较小,所以我们可以直接枚举最远的池塘数来计算最大值。 2. 2. 2. 我们可以提前把路程减去,然后只剩下钓鱼的时间了,所以就相当于在这多个鱼塘里钓,由于钓一次都是一分钟,并且没有路程的计算,所以就挑最大的几个就行了,也就是多个数 a [ i ] a[i] a[i] ,每个数取了就递减 d [ i ] d[i] d[i] 个,求最多能取多少个数,直接拿堆来模拟即可。

题目描述:

有 N 个鱼塘排成一排,每个鱼塘中有一定数量的鱼,例如:N=5 时,如下表:鱼塘编号	                                       1	2	3	4	5
第1分钟能钓到的鱼的数量(1..1000)	              10	14	20	16	9
每钓鱼1分钟钓鱼数的减少量(1..100)	               2	4	6	5	3
当前鱼塘到下一个相邻鱼塘需要的时间(单位:分钟)	3	5	4	4	
即:在第 1 个鱼塘中钓鱼第 1 分钟内可钓到 10 条鱼,第 2 分钟内只能钓到 8 条鱼,……,第 5 分钟以后再也钓不到鱼了。从第 1 个鱼塘到第 2 个鱼塘需要 3 分钟,从第 2 个鱼塘到第 3 个鱼塘需要 5 分钟,……给出一个截止时间 T,设计一个钓鱼方案,从第 1 个鱼塘出发,希望能钓到最多的鱼。假设能钓到鱼的数量仅和已钓鱼的次数有关,且每次钓鱼的时间都是整数分钟。输入格式
共 5 行,分别表示:
第 1 行为 N;
第 2 行为第 1 分钟各个鱼塘能钓到的鱼的数量,每个数据之间用一空格隔开;
第 3 行为每过 1 分钟各个鱼塘钓鱼数的减少量,每个数据之间用一空格隔开;
第 4 行为当前鱼塘到下一个相邻鱼塘需要的时间;
第 5 行为截止时间 T。输出格式
一个整数(不超过231−1),表示你的方案能钓到的最多的鱼。数据范围
1≤N≤100 ,1≤T≤1000
输入样例:
5
10 14 20 16 9
2 4 6 5 3
3 5 4 4
14
输出样例:
76

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;const int N = 110;int n, T;
int a[N], d[N], l[N];LL work(int x, int t)
{if(t <= 0) return 0;priority_queue<PII> heap;for(int i = 1; i <= x; ++i) heap.push({a[i], i});LL res = 0;while(t-- && heap.size()){auto t1 = heap.top(); heap.pop();int v = t1.first, p = t1.second;res += v;if(v - d[p] > 0) heap.push({v-d[p], p});}return res;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n;for(int i = 1; i <= n; ++i) cin >> a[i];for(int i = 1; i <= n; ++i) cin >> d[i];for(int i = 2; i <= n; ++i) {cin >> l[i];l[i] += l[i-1];}cin >> T;LL res = 0;for(int i = 1; i <= n; ++i){res = max(res, work(i, T - l[i]));}cout << res << endl;
}

二、技能升级

标签:多路归并

思路:明显可以看出这道题是上一道题的简化版,也就是这道题是包含在上道题里的,也就是 w o r k work work 函数,但由于这道题的 M M M 的值比较大,所以如果用 h e a p heap heap 来做的话,能过 7 12 \frac{7}{12} 127 个数据,所以要另辟蹊径了。我们假设所有的可能的数第 M M M 个数值为 mid ,那么最大值就是取前 M M M 个数了,所以我们只要 mid 确定了下来,剩余就可以遍历每个序列用数学公式就能计算出来总和。然后我们能够知道小于等于 mid 的个数一定是大于等于 M 的,所以具有二段性可以用二分来写,具体细节见代码。

题目描述:

小蓝最近正在玩一款 RPG 游戏。他的角色一共有 N 个可以加攻击力的技能。其中第 i 个技能首次升级可以提升 Ai 点攻击力,以后每次升级增加的点数都会减少 Bi。⌈AiBi⌉(上取整)次之后,再升级该技能将不会改变攻击力。现在小蓝可以总计升级 M 次技能,他可以任意选择升级的技能和次数。请你计算小蓝最多可以提高多少点攻击力?输入格式
输入第一行包含两个整数 N 和 M。
以下 N 行每行包含两个整数 Ai 和 Bi。输出格式
输出一行包含一个整数表示答案。数据范围
对于 40% 的评测用例,1≤N,M≤1000;
对于 60% 的评测用例,1≤N≤104,1≤M≤107;
对于所有评测用例,1≤N≤105,1≤M≤2×109,1≤Ai,Bi≤106。输入样例:
3 6
10 5
9 2
8 1
输出样例:
47

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;const int N = 1e5+10;int n, m;
int a[N], b[N];bool check(int mid)
{LL sum = 0;for(int i = 1; i <= n; ++i){if(a[i] >= mid){sum += (a[i] - mid) / b[i] + 1;}}return sum >= m;
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> n >> m;for(int i = 1; i <= n; ++i) cin >> a[i] >> b[i];int l = 0, r = 1e6;while(l < r){int mid = (LL)l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}LL res = 0, cnt = 0;for(int i = 1; i <= n; ++i){if(a[i] >= r){int c = (a[i] - r) / b[i] + 1;int end = a[i] - (c - 1) * b[i];cnt += c;res += (LL)(a[i] + end) * c / 2;}}cout << res - (cnt - m) * r << endl;  // 可能会有多个r,数量超过了mreturn 0;
}

三、序列

标签:多路归并

思路:这是一个典型的从 m m m n n n 列中,每一行选一个数组,求选到的数字之和最小的 n n n 个。我们可以先两行两行的合并找到最小的 n n n 个,然后遍历 m − 1 m - 1 m1 次,这样最后的 n n n 个数字就是最小的了。然后两个合并,我们可以先把 a a a 数组排个序,然后把这 n 2 n ^ 2 n2 的数排成 n n n 组,如下图所示,由于 a a a 是排好序了,所以每组最小的就是最前边的那个,然后把这 n n n 个数加入到堆中,然后记下当前下标,然后再变成每组下一个数即可,这样下来的 n n n 个数就是最小的了。
在这里插入图片描述

题目描述:

给定 m 个序列,每个包含 n 个非负整数。现在我们可以从每个序列中选择一个数字以形成具有 m 个整数的序列。很明显,我们一共可以得到 nm 个这种序列,然后我们可以计算每个序列中的数字之和,并得到 nm 个值。现在请你求出这些序列和之中最小的 n 个值。输入格式
第一行输入一个整数 T,代表输入中包含测试用例的数量。接下来输入 T 组测试用例。对于每组测试用例,第一行输入两个整数 m 和 n。接下在 m 行输入 m 个整数序列,数列中的整数均不超过 10000。输出格式
对于每组测试用例,均以递增顺序输出最小的 n 个序列和,数值之间用空格隔开。每组输出占一行。数据范围
0<m≤1000,0<n≤2000
输入样例:
1
2 3
1 2 3
2 2 3
输出样例:
3 3 4

示例代码:

#include <bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int,int> PII;const int N = 2010;int T;
int m, n;
int a[N], b[N], c[N];void merge()
{priority_queue<PII, vector<PII>, greater<PII>> heap;for(int i = 0; i < n; ++i) heap.push({a[0] + b[i], 0});for(int i = 0; i < n; ++i){auto t = heap.top(); heap.pop();int v = t.first, p = t.second;c[i] = v;heap.push({v - a[p] + a[p+1], p+1});}memcpy(a, c, sizeof a);
}int main()
{ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin >> T;while(T--){cin >> m >> n;for(int i = 0; i < n; ++i) cin >> a[i];sort(a, a+n);for(int i = 0; i < m - 1; ++i){for(int j = 0; j < n; ++j) cin >> b[j];merge();}for(int i = 0; i < n; ++i) cout << a[i] << " ";cout << endl;}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_999294.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

JVM-垃圾收集器G1

G1垃圾回收器 概述&#xff1a; 是一款面向服务器的垃圾收集器,主要针对配备多个处理器及大容量内存的机器. 以极高效率满足GC停顿时间要求的同时,还具备高吞吐量性能特征.G1保留了年轻代和老年代的概念&#xff0c;但不再是物理隔阂了&#xff0c;它们都是&#xff08;可以不连…

前端javascript的DOM对象操作技巧,全场景解析

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; 所属的专栏&#xff1a;前端泛海 景天的主页&#xff1a;景天科技苑 文章目录 1.js的DOM介绍2.节点元素层级关系3.通过js修改&#xff0c;清空节点…

Matlab|基于目标级联法的微网群多主体分布式优化调度

目录 主要内容 1.1 上层微网群模型 1.2 下层微网模型 部分程序 实现效果 下载链接 主要内容 本文复现《基于目标级联法的微网群多主体分布式优化调度》文献的目标级联部分&#xff0c; 建立微网群系统的两级递阶优化调度模型: 上层是微网群能量调度中心优化调度…

Awesome-Backbones-main——alexnet模型分析

AlexNet作为骨干网络相对较老&#xff0c;可能在复杂数据集上的表现不如一些最新的深度网络结构&#xff0c;如ResNet、EfficientNet等&#xff0c;学习率调整策略中采用了阶梯式学习率更新器&#xff0c;可能并不总是适合所有数据集和模型&#xff0c;需要根据具体情况调整学习…

vue 使用 PrintJs 实现打印pdf效果

一、print.js介绍 Print.js主要是为了帮助我们直接在应用程序中打印PDF文件&#xff0c;而无需离开界面&#xff0c;并且不使用嵌入。对于用户不需要打开或下载PDF文件的特殊情况&#xff0c;他们只需要打印它们。 例如&#xff0c;当用户请求打印在服务器端生成的报告时&…

【刷题记录】详谈设计循环队列

下题目为个人的刷题记录&#xff0c;在本节博客中我将详细谈论设计循环队列的思路&#xff0c;并给出代码&#xff0c;有需要借鉴即可。 题目&#xff1a;LINK 循环队列是线性表吗&#xff1f;或者说循环队列是线性结构吗&#xff1f; 对于这个问题&#xff0c;我们来看一下线…

C语言之练手题

题目1&#xff1a; 思路&#xff1a;我们定义两个变量left和right分别为数组的左端下标和右端下标。 左端下标的元素为奇数时&#xff0c;left继续往前走&#xff0c;为偶数时就停下 右端下标的元素为偶数时&#xff0c;right- -往回走&#xff0c;为奇数时停下 停下后对应的元…

云计算 3月8号 (wordpress的搭建)

项目wordpress 实验目的&#xff1a; 熟悉yum和编译安装操作 锻炼关联性思维&#xff0c;便于以后做项目 nginx 编译安装 1、安装源码包 [rootlinux-server ~]# yum -y install gcc make zlib-devel pcre pcre-devel openssl-devel [rootlinux-server ~]# wget http://nginx.…

Python 对Excel工作表中的数据进行排序

在Excel中&#xff0c;排序是整理数据的一种重要方式&#xff0c;它可以让你更好地理解数据&#xff0c;并为进一步的分析和报告做好准备。本文将介绍如何使用第三方库Spire.XLS for Python通过Python来对Excel中的数据进行排序。包含以下三种排序方法示例&#xff1a; 按数值…

WPF Border控件 基本使用

Border 基本使用 1单线效果 代码&#xff1a; <Border Grid.Row"0" BorderThickness"0,0,0,1" BorderBrush"Red" /> 说明&#xff1a; BorderThickness"0,0,0,1" 可以分别设置四条边&#xff0c;顺序是&#xff1a;左 上 右…

tcp服务器客户端通信(socket编程)

目录 1.编程流程 2.代码演示 2.1 服务器代码 2.2 客户端代码 3.注意 3.1 ping命令 3.2 netstat命令 3.3 为什么memset? 3.4 哪个会阻塞? 3.5 显示连接信息 1.编程流程 2.代码演示 2.1 服务器代码 #include <stdio.h> #include <stdlib.h> #include <…

ArmSoM Rockchip系列产品 通用教程 之 UART 使用

1. UART 简介​ Rockchip UART (Universal Asynchronous Receiver/Transmitter) 基于16550A串口标准&#xff0c;完整模块支持以下功能&#xff1a; 支持5、6、7、8 bits数据位。支持1、1.5、2 bits停止位。支持奇校验和偶校验&#xff0c;不支持mark校验和space校验。支持接…

git分布式管理-头歌实验标签

一、创建标签 任务描述 现在你已经成了项目负责人&#xff0c;由你负责发布版本&#xff0c;你需要在发布一个版本之前&#xff0c;给该版本对应的代码打上标签&#xff0c;以便于管理和标识。 本关任务&#xff1a;为最近一次提交打上标签。 相关知识 在开发过程中&#xff0c…

【论文阅读】High-Resolution Image Synthesis with Latent Diffusion Model

High-Resolution Image Synthesis with Latent Diffusion Model 引用&#xff1a; Rombach R, Blattmann A, Lorenz D, et al. High-resolution image synthesis with latent diffusion models[C]//Proceedings of the IEEE/CVF conference on computer vision and pattern re…

免费的文案二次创作软件,打造高质量原创文案

在当今数字化时代&#xff0c;内容创作已经成为企业和个人推广自身品牌、产品和服务的重要手段。然而&#xff0c;对于许多人来说&#xff0c;撰写高质量的原创文案并非易事。幸运的是&#xff0c;随着技术的发展&#xff0c;出现了许多文案二次创作免费软件&#xff0c;为那些…

基于ACM32 MCU的电动滑板车方案介绍

随着智能科技的快速发展&#xff0c;电动滑板车的驱动系统也得到了长足的发展。国内外的电动滑板车用电机驱动系统分为传统刷式电机和无刷电机两种类型。其中&#xff0c;传统的刷式电机已经逐渐被无刷电机所取代&#xff0c;无刷电机的性能和寿命都更出色&#xff0c;已成为电…

Git分布式管理-头歌实验分支管理

一、创建本地分支-git branch 任务描述 当你进入一个团队&#xff0c;在获得产品的完整代码之后&#xff0c;你首先要做的就是&#xff0c;在本地创建一个属于自己的分支&#xff0c;然后才能在自己的分支上进行开发。 本关任务&#xff1a;在本地仓库创建一个新的分支&#xf…

gitte上传项目操作

一、项目背景 打比赛&#xff0c;多个人合作&#xff0c;选择github&#xff0c;顺便了解下git的代码操作。 二、步骤 2.1 新建仓库 2.2 打开你要上传到库的项目 2.2 选择 Git Bash Here 输入指令 git init 2.3 查找github的仓库 2.2 将文件放入暂缓区 git add . 2.3填写…

什么是AJAX?它的运用场景有哪些?

文章目录 前言一、什么是AJAX二、AJAX原理是什么三、为什么需要AJAX四、AJAX的使用五、AJAX的应用场景 前言 AJAX 即 Asynchronous Javascript And XML&#xff08;异步JavaScript和XML&#xff09;&#xff0c;是指一种创建交互式网页应用的网页开发技术。 AJAX 是一种用于创…

186基于matlab的信号盲源分离算法

基于matlab的信号盲源分离算法&#xff0c;包括变步长盲源分离&#xff08;EASI&#xff09;,RLS(自然梯度和普通梯度)&#xff0c;并将三种方法分离结果进行对比。程序已调通&#xff0c;可直接运行。 186 信号盲源分离算法 变步长盲源分离 (xiaohongshu.com)