建设集团网站公司,网页页面布局,江宁做网站价格,邯郸信息港交友目录 引言概念一、鱼塘钓鱼二、技能升级三、序列 引言
关于这个多路并归蓝桥杯考的不是很多#xff0c;如果要出的话#xff0c;可能模型都会差不多#xff0c;因为不会出太难的题#xff0c;难题基本上都是贪心、DP之类的#xff0c;所以好好刷题刷熟练就行了#xff0… 目录 引言概念一、鱼塘钓鱼二、技能升级三、序列 引言
关于这个多路并归蓝桥杯考的不是很多如果要出的话可能模型都会差不多因为不会出太难的题难题基本上都是贪心、DP之类的所以好好刷题刷熟练就行了见过熟悉即可加油 概念
多路归并首先可以参考博客算法刷题归并排序、归并排序这个多路归并其实就是一种类型的题目还是要因题而异。 一、鱼塘钓鱼
标签多路归并
思路 1. 1. 1. 首先核心就是则个人钓鱼不会折返跑因为每个鱼塘钓的鱼的数量是和你钓的次数有关和时间无关如果你又折返跑回来钓的话还不如就直接在上一次的鱼塘多钓几次还浪费路上的时间所以最优解肯定是一条直线而不会是来回的跑因为这个 N N N 比较小所以我们可以直接枚举最远的池塘数来计算最大值。 2. 2. 2. 我们可以提前把路程减去然后只剩下钓鱼的时间了所以就相当于在这多个鱼塘里钓由于钓一次都是一分钟并且没有路程的计算所以就挑最大的几个就行了也就是多个数 a [ i ] a[i] a[i] 每个数取了就递减 d [ i ] d[i] d[i] 个求最多能取多少个数直接拿堆来模拟即可。
题目描述
有 N 个鱼塘排成一排每个鱼塘中有一定数量的鱼例如N5 时如下表鱼塘编号 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.husing namespace std;typedef long long LL;
typedef pairint,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_queuePII 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≤1041≤M≤107
对于所有评测用例1≤N≤1051≤M≤2×1091≤Ai,Bi≤106。输入样例
3 6
10 5
9 2
8 1
输出样例
47示例代码
#include bits/stdc.husing namespace std;typedef long long LL;const int N 1e510;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 m−1 次这样最后的 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 个序列和数值之间用空格隔开。每组输出占一行。数据范围
0m≤1000,0n≤2000
输入样例
1
2 3
1 2 3
2 2 3
输出样例
3 3 4示例代码
#include bits/stdc.husing namespace std;typedef long long LL;
typedef pairint,int PII;const int N 2010;int T;
int m, n;
int a[N], b[N], c[N];void merge()
{priority_queuePII, vectorPII, greaterPII 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[p1], p1});}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, an);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;
}
