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

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，填充的值为 1
        vector<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 × 5
            v[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;
}