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.技能升级

思路

二分第 m 次升级的技能攻击力，然后大于这个攻击力的就累加求和，去除多余的数

#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.谦虚数字

思路

比如，集合是【2，3，5】，最开始会有3个空的queue，然后把{2, 0}，{3, 1}，{5, 2} 放入priority queue中({2, 0}，表示第0个质数的queue的front是2)，我们pop这个{2, 0}，然后把2 × 2， 2 × 3， 2 × 5分别加入三个质数对应的queue中，因为这次我们取走的是来自质数2的queue里的数，所以我们要把这个queue的front加入priority queue中。
那么，现在的状态是priority queue中是{3, 1}，{4, 0}，{5, 2}。
三个queue中是[],[6],[10]

#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.序列

思路

排序 a 数组，分成 n 个组，每次取最小值

#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;
}