蓝桥杯2024年第十五届省赛真题-训练士兵

解题思路:

按照训练次数从小到大排序， 从训练次数少的开始枚举，贪心找单独训练还是组团训练

注意事项:

参考代码:

#include <bits/stdc++.h>
#define int long long
using namespace std;

struct A {
    int val, cnt;
}f[100010];

// res 表示总消耗金币数量
int n, m, res;

// 按照次数从小到大排序
bool is(A a, A b) {
    return a.cnt < b.cnt;
}

signed main() {
    
    cin >> n >> m;

    // a 表示从第 i 个士兵到第 n 个士兵每个训练一次的总和

    int a = 0;
    for(int i = 1; i <= n; i++) {
        cin >> f[i].val >> f[i].cnt;
        a += f[i].val;
    }
    
    sort(f + 1, f + n + 1, is);
    
    // tk 表示组团训练的次数
    int tk = 0;
    for(int i = 1; i <= n; i++) {
        /*
            如果组团总次数大于等于这个士兵需要训练的次数
            说明这个士兵不用训练了，更新 a 的值
        */
        if(f[i].cnt <= tk) {
            a -= f[i].val;
            continue;
        }
        
        /*
            如果组团训练比较划算，比从现在开始到第 n 个士兵单独训练一次划算
            就组团训练 f[i][1] - tk表示这个士兵还需要训练几次    
        */
        if(a >= m) {        
            // 总额加上这个士兵需要组团训练的次数
            res += (f[i].cnt - tk) * m;
            // 更新组团训练次数
            tk += f[i].cnt - tk;
        } else {
            res += (f[i].cnt - tk) * f[i].val;
        }
        a -= f[i].val;
    }
    
    cout << res << endl;
    
    return 0;
}