Hello大家好，我是秋刀鱼，今天又来给大家更新蓝桥杯真题题解了。
今天的题目不算太难，不过需要注意的细节还是很多，无论是日常的刷题还是比赛编写代码时一定要注意细节部分，不要因为疏忽导致失分。
如果觉得作者写的还不错的朋友可以一键三连支持一下！ ?( ′･?･` )比心
往期蓝桥杯算法解析：
【蓝桥杯冲刺 day8】题目全解析 —附上LeetCode 每日一题
【蓝桥杯冲刺 day7】 题目全解析 — 附上LeetCode周赛 银联-03. 理财产品
打水问题
题目描述
N个人要打水，有M个水龙头，第i个人打水所需时间为Ti，请安排一个合理的方案使得所有人的等待时间之和尽量小。
提示
一种最佳打水方案是，将N个人按照Ti从小到大的顺序依次分配到M个龙头打水。
例如样例中，Ti从小到大排序为1，2，3，4，5，6，7，将他们依次分配到3个龙头，则去龙头一打水的为1，4，7；去龙头二打水的为2,5；去第三个龙头打水的为3,6。
第一个龙头打水的人总等待时间 = 0 + 1 + (1 + 4) = 6
第二个龙头打水的人总等待时间 = 0 + 2 = 2
第三个龙头打水的人总等待时间 = 0 + 3 = 3
所以总的等待时间 = 6 + 2 + 3 = 11输入
第一行两个正整数N M 接下来一行N个正整数Ti。
N,M< =1000，Ti< =1000输出
最小的等待时间之和。（不需要输出具体的安排方案）
样例输入复制
7 3 3 6 1 4 2 5 7样例输出复制
11
题目解析
核心思路是贪心，确实还是第一次见有题目直接把核心的思路写在题目里面 😆
代码部分就是简单地实现题目中的核心思路，不过多的赘述。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <queue>
using namespace std;
#define M 1001
int main()
{
int n, k;
int time[M];
for (int i = 1; i <= n; ++i) {
cin >> time[i - 1];
}
// 按照时间顺序排序
sort(time, time + n);
int ans = 0;
for (int i = k; i <= n; ++i) {
ans += time[i] - time[i - k];
}
cout << ans;
return 0;
}
思考1：为什么这样分配水龙头等待的时间之和会是最短的呢？
因为基于贪心的思想，为了使总等待时间最少，那么水龙头会优先分配给打水所需时间最少的人，也就是说，刚开始时，水龙头一定会分给所需时间最少的 K K K 个人。如果将顺序数组按顺序 K K K 个人当做一组，那么第二组：也就是排序后索引为 [ K , 2 ? K ) [K,2*K) [K,2?K) 的这些人一定是下一批分配水头的，只有第二组人均被分配水龙头后，第三组的人才能被分配水龙头。
那么现在问题来了，第一组第一个人最先完成，优先给第二组的哪一个人分配水龙头呢？
答案是，第二组的任意一个人都可以。假设第 i i i 个人打水时间为 t i m e i time_i timei? ，那么无论怎么分配水龙头，第二组所有成员等待的时间和一定是： ∑ i = 0 K ? 1 t i m e i \displaystyle \sum^{K-1}_{i = 0} time_i i=0∑K?1?timei? ，无论如何分配都是这个值，所以第二组任意一个人都可以得到空闲的水龙头。
夺宝奇兵
题目描述
在一座山上,有很多很多珠宝,它们散落在山底通往山顶的每条道路上,不同道路上的珠宝的数目也各不相同.下图为一张藏宝地图:
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5”夺宝奇兵”从山下出发,到达山顶,如何选路才能得到最多的珠宝呢?在上图所示例子中,按照5-> 7-> 8-> 3-> 7的顺序,将得到最大值30
输入
第一行正整数N(100> =N> 1),表示山的高度
接下来有N行非负整数,第i行有i个整数(1< =i< =N),表示山的第i层上从左到右每条路上的珠宝数目输出
一个整数,表示从山底到山顶的所能得到的珠宝的最大数目.
样例输入复制
5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5样例输出复制
30
写在前面
这道题或多或少优点坑了😢
根本没有规定移动路径，只是简简单单提了句从山底到山顶，如果是我我完全能够拿完全部的珠宝，当然这样题目就太简单了。在很多次wa后发现这题只能往上走或左上行走，所有友友们要注意一下。
题目解析
一道基础的动态规划题目。动态规划作为蓝桥杯的必考知识点，十分重要！如果还没有学习过动态规划一定要预先学习！
定义 d p [ i ] [ j ] dp[i][j] dp[i][j] 存放 第 i i i 行，第 j j j 个位置时，所获得的珠宝最大数目。虽然说题目给定是从山底到山顶，但是也同样可以反推：从山顶到山底收获宝藏的最大值，移动时只能向下或右下方向。
对于
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j] 的值有两种可能：要么带上 上方的宝藏下来，要么带上左上方的宝藏下来，这两种可能会发生，因此我们还需要找到两种可能的最大值就是我们所需要的值，dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])
#include <bits/stdc++.h>
using namespace std;
#define M 101
int main()
{
// 边界不保留元素，防止出界
int dp[M+1][M+1]{ {0} };
int n;
cin >> n;
int ans = -11111;
for (int i = n - 1; i >= 0; --i) {
for (int j = 1; j <= n - i; ++j) {
cin >> dp[i][j];
if (i != n - 1) {
dp[i][j] += max(dp[i + 1][j - 1], dp[i + 1][j]);
}
if (i == 0) {
ans = max(ans, dp[i][j]);
}
}
}
cout << ans;
return 0;
}
同样的动态规划问题在很多情况下都能压缩 d p dp dp 数组，本题因为状态只来自于上一行的数据，因此只需要记录上一行的左上角数据于上方数据，就能使用一维数组实现：
#include<bits/stdc++.h>
using namespace std;
#define M 101
int main()
{
int dp[M+1]{ 0 };
int n;
cin >> n;
int ans = -11111;
int leftTop;
for (int i = n - 1; i >= 0; --i) {
// 保存左上角值
leftTop = 0;
for (int j = 1; j <= n - i; ++j) {
// 保留顶部的值
int top = dp[j];
cin >> dp[j];
if (i != n - 1) {
dp[j] += max(top, leftTop);
leftTop = top;
}
// cout << i << " " << j <<" " << dp[j] << endl;
if (i == 0) {
ans = max(ans, dp[j]);
}
}
}
cout << ans;
return 0;
}
调手表
题目描述
小明买了块高端大气上档次的电子手表，他正准备调时间呢。
在 M78 星云，时间的计量单位和地球上不同，M78 星云的一个小时有 n 分钟。
大家都知道，手表只有一个按钮可以把当前的数加一。在调分钟的时候，如果当前显示的数是 0 ，那么按一下按钮就会变成 1，再按一次变成 2 。如果当前的数是 n - 1，按一次后会变成 0。
作为强迫症患者，小明一定要把手表的时间调对。如果手表上的时间比当前时间多 1，则要按 n - 1次加一按钮才能调回正确时间。
小明想，如果手表可以再添加一个按钮，表示把当前的数加 k 该多好啊…
他想知道，如果有了这个 +k 按钮，按照最优策略按键，从任意一个分钟数调到另外任意一个分钟数最多要按多少次。
注意，按 +k 按钮时，如果加 k 后数字超过 n-1,则会对 n 取模。
比如，n=10, k=6 的时候，假设当前时间是 0，连按 2 次 +k 按钮，则调为 2。
输入描述
一行两个整数 n, k （0 < k < n < 10^5），意义如题。
输出描述
输出一行一个整数，表示按照最优策略按键，从一个时间调到另一个时间最多要按多少次。
输入输出样例
示例
输入
5 3输出
2样例解释
如果时间正确则按 0 次。否则要按的次数和操作系列之间的关系如下：
1：+1
2：+1, +1
3：+3
4：+3, +1
解题思路
多重背包思路（超时）
本题的数据相当刁钻，数据量高达 1 0 5 10^5 105 ，也就是说一般思路的多重背包问题并不适合作为本题的解决方法，因为背包问题的时间复杂度通常会达到 O ( N 2 ) O(N^2) O(N2) ，
不过多重背包的思路仍然可以学习：
多重背包问题通常是给定一个重量weight，给定很多商品的价值value[]、重量weight[]，并且每一个商品都能被无限次地购买，问该背包重量下最大购买的商品价值。
- 因为每一次能够跳跃 1 1 1 或 K K K 次，且可以进行无数次地跳跃，可以将其当做商品价值
- 每一个时刻距离 0 时 刻 0时刻 0时刻 位置可以当做给定的背包重量。
这样就能将问题转换为多重背包问题，因为没有AC，所以就不附上代码了。
宽度优先遍历BFS
既然多重背包没办法解决，可以转变下思路，既然需要找到最大次数，使用BFS算法是一定能够求解的，且寻找的是最短的最大次数，因此BFS算法高于DFS算法，于是可以有如下的尝试：
#include<bits/stdc++.h>
using namespace std;
#define M 10010
#define INTMIN -2e6
int ans[M];
void bfs(int n, int k) {
queue<int>qu;
qu.push(0);
int time = 0;
int t = 0;
while (qu.size()) {
int len = qu.size();
for (int i = 0; i < len; ++i) {
int idx = qu.front();
qu.pop();
if (ans[idx] <0 ) {
++t;
ans[idx] = time;
}
if (t == n) {
return;
}
int nx1 = (idx + n + 1) % n;
int nx2 = (idx + k + n) % n;
if (ans[nx1] < 0) {
qu.push(nx1);
}
if (ans[nx2] < 0) {
qu.push(nx2);
}
}
++time;
}
}
int main()
{
int n, k;
memset(ans, INTMIN, sizeof(ans));
cin >> n >> k;
bfs(n, k);
int m = -1;
for (int i = 0; i < n; ++i) {
m = max(m, ans[i]);
}
cout << m;
return 0;
}
结果还是没能成功AC，原因主要有如下几点：
- 数据量过大，重复遍历次数过多
- 最后一次循环遍历数据量巨大，浪费大量时间
优化思路如下：
- 对于 +1 这种来说，电子表的时间从 n ? 1 ? ? > 0 n-1~ -> 0 n?1??>0 调整次数为 n n n ，但是考虑到从 n ? k n-k n?k 通过 +K 操作同样到 0 调整总次数为 n ? k + 1 n-k+1 n?k+1 ，而 k > 0 k>0 k>0 ，因此： n > = n ? k + 1 n>=n-k+1 n>=n?k+1 ，所以当时间超过n-1时跳转为0的情况均不需要考虑+1，实现剪枝操作
- 在上面的代码中，判断退出放在了取出队列元素的操作之后，也就是说 w h i l e while while 会多执行一轮循环才会返回结果。只需要将判断运算放在取出队列元素的操作之前，就可以省去不必要的一轮 w h i l e while while 循环
#include<bits/stdc++.h>
using namespace std;
int ans[100001];
struct node {
int i;
int t;
node(int i, int t) {
this->i = i;
this->t = t ;
}
};
int main()
{
int n, k,bk;
cin >> n >> k;
queue<node>qu;
qu.push(node(0, 0));
while (!qu.empty())
{
node cur = qu.front();
qu.pop();
int idx = cur.i;
int t = cur.t;
++t;
int nx1 = idx + 1;
int nx2 = (idx + k) % n;
// 先判断后在推入元素 同时判断 nx1是否大于n-1进行剪枝
if (nx1 < n && !ans[nx1]) {
ans[nx1] = t;
qu.push(node(nx1, t));
}
if (!ans[nx2]) {
ans[nx2] = t;
qu.push(node(nx2, t));
}
}
bk = 0;
for (int i = 1; i < n; i++)
{
bk = max(ans[i], bk);
}
cout << bk;
return 0;
}
写在最后
代码、论述中有任何问题，欢迎大家指出，同时如果有任何疑问，也能够在评论区中留言，大家共同讨论共同进步！
