## 蓝桥杯练习题——多路并归

news/2024/5/30 1:11:36/文章来源:https://blog.csdn.net/qq_62734493/article/details/136664713

## 1.鱼塘钓鱼

### 思路

``````#include<iostream>
#include<queue>
using namespace std;
const int N = 110;
int a[N], b[N], c[N];
int n, t;// 当前最后走到的鱼塘，还剩的时间和
int ff(int u, int sum){// 大根堆，堆顶存储最大值priority_queue<pair<int, int>> q;// 把已经经过的鱼塘入队for(int i = 1; i <= u; i++){q.push({a[i], b[i]});}int res = 0;// 当时间还没过完while(sum--){auto it = q.top();res += it.first;q.push({max(it.first - it.second, 0), it.second});q.pop();}return res;
}int main(){scanf("%d", &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);for(int i = 1; i <= n; i++) scanf("%d", &b[i]);for(int i = 1; i < n; i++) scanf("%d", &c[i]); scanf("%d", &t);int ans = 0;for(int i = 1; i <= n && t > 0; i++){// 求最大值ans = max(ans, ff(i, t));// 每次向后再取一个鱼塘t -= c[i];}printf("%d", ans);return 0;
}
``````

## 2.技能升级

### 思路

``````#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int a[N], b[N];
int n, m;int check(int x){long long cnt = 0;for(int i = 0; i < n; i++){if(a[i] >= x) cnt += (a[i] - x) / b[i] + 1;}return cnt >= m;
}int main(){scanf("%d%d", &n, &m);for(int i = 0; i < n; i++) scanf("%d%d", &a[i], &b[i]);// 二分第 m 次升级的技能增加的攻击力int l = 0, r = 1e6 + 1;while(l + 1 < r){int mid = (l + r) / 2;if(check(mid)) l = mid;else r = mid;}long long sum = 0, res = 0;for(int i = 0; i < n; i++){if(a[i] > l){// 计算项数int cnt = (a[i] - l) / b[i] + 1;// 计算最后一个数int ed = a[i] - b[i] * (cnt - 1);// 累加技能升级的总和sum += 1ll * (a[i] + ed) * cnt / 2;// 累加升级的个数，可能会有多余res += cnt;}}// 总的和减去多余的升级和printf("%lld", sum - (res - m) * l);return 0;
}
``````

## 3.丑数

### 思路

``````class Solution {
public:int getUglyNumber(int n) {// 容器大小为 1，填充的值为 1vector<int> q(1, 1);// 枚举 2 3 5 的倍数int i = 0, j = 0, k = 0;// 只需要循环 n - 1 次while(--n){int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));q.push_back(t);if(t == q[i] * 2) i++;if(t == q[j] * 3) j++;if(t == q[k] * 5) k++;}return q.back();}
};
``````

## 4.谦虚数字

### 思路

``````#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 110;
// 小根堆存储当前最小的谦虚数字
priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> q;
// 存储所有的谦虚数字
queue<long long> v[N];
int p[N];
int k, n;signed main(){scanf("%d%d", &k, &n);for(int i = 1; i <= k; i++){scanf("%d", &p[i]);// 把 {2, 1}，{3, 2}，{5, 3} 放入q.push({p[i], i});}int res = 0;for(int i = 1; i <= n; i++){// 取出当前最小的谦虚数字, {2, 1}auto it = q.top();q.pop();long long a = it.first, b = it.second;res = a;for(int j = b; j <= k; j++){// 加入 2 × 2， 2 × 3， 2 × 5v[j].push(p[j] * a);if(b == j){// {3, 2}，{4, 1}，{5, 3}q.push({v[j].front(), j});// [], [6], [10]v[j].pop();}}}printf("%d", res);return 0;
}
``````

## 5.序列

### 思路

``````#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N = 2e3 + 10;
int a[N], b[N], c[N];
int m, n;// 每次合并 a b 数组
void merge(){// 小根堆，存储 a 和 b 的和，下标priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q; // 先存储每组第一个数for(int i = 1; i <= n; i++){q.push({a[1] + b[i], 1});}for(int i = 1; i <= n; i++){auto it = q.top();q.pop();int x = it.first, y = it.second;c[i] = x;// a[1] + b[1] -> a[2] + b[1]q.push({x - a[y] + a[y + 1], y + 1});}for(int i = 1; i <= n; i++) a[i] = c[i];
}int main(){int t;scanf("%d", &t);while(t--){scanf("%d%d", &m, &n);for(int i = 1; i <= n; i++) scanf("%d", &a[i]);sort(a + 1, a + n + 1);for(int i = 1; i <= m - 1; i++){for(int i = 1; i <= n; i++) scanf("%d", &b[i]);merge();}for(int i = 1; i <= n; i++) printf("%d ", a[i]);printf("\n");}return 0;
}
``````

### Sui技术帮助Studio Mirai成功实现创意愿景

Brian和Ben Li兄弟对艺术充满热情&#xff0c;通过共同创立的研发工作室Studio Mirai&#xff0c;他们正在探索Web3技术与创意产业的交集。 Studio Mirai的第一个头像类项目&#xff08;profile picture&#xff0c;PFP&#xff09;Tamashi存在于Nozomi World中&#xff0c;这…

### C++ 改造红黑树,封装map和set

C 改造红黑树,封装map和set 一.前言:已经实现好了的红黑树二.简化STL库里面对于map和set的封装1.STL库中红黑树的简化代码2.STL库中set的简化代码3.STL库中map的简化代码4.封装map和set的第一步5.红黑树第一个模板参数的价值6.红黑树节点的定义 三.仿函数1.解除仿函数的误解2.仿…

### devops-git【部署及配置】

1、安装Git Linux做为服务器端系统&#xff0c;Windows作为客户端系统&#xff0c;分别安装Git&#xff1a; 【服务器端】 输入git --version 若出现 -bash:git:command not found则需要安装git&#xff1b;服务器端&#xff1a;输入yum -y install git安装完后&#xff0c;…

### 【idea】正则表达式去除项目中的各种注释

【ctrlshiftr】 整个项目全局选择正则表达式Regex 【ctrlr】当前页面 分别输入以下命令 ^\s*\n #去除空行 ^\s*\n# 去除 <!--xxx--> 注释 <!--.*?--># 删除 java 注释 // xxx //[\s\S]*?\n# 删除 java 注释 /* */ /\*{1,2}[\s\S]*?\*/替换全部 Replace all 为…