详情请见博客 训练士兵
解题思路
要想将所有士兵升级为满级，要么组团训练，要么一个一个单独训练，为了使花费的金币最少，那么只需要在每次升级的时候比较组团训练的费用和一个一个单独训练的费用即可，谁便宜选谁。那么可以设每次所有没有满级的士兵单独训练的花费总和为sum_cost，那么sum_cost的初始值为所有士兵每次升级的花费之和（所有士兵一开始不是满级）。然后我们将最大的训练次数保存下来，用max_t来表示。

最后再遍历训练次数for(int i=1;i<=max_t;i++)，然后比较是组团训练更便宜还是单独训练更便宜，最后的答案ans+=便宜的训练。但是遍历升级次数的过程，会有士兵已经升级到满级了，所以sum_cost是变化的。比如上述样例，当进行两次组团训练后，第一个士兵和第3个士兵就满级了，无须继续训练，这时所有未满级的士兵一个一个单独训练升一级的花费为2，小于组团训练花费的6，所以这个时候应该让未满级的士兵单独训练。因此我们可以设定一个哈希表a[N]，a[i]=k，表示所有需要i次就能满级的士兵单次升级花费之和为k，如上述样例中第一个士兵和第三个士兵需要升级两次就能满级的士兵单次升级花费之和为5+3=8，即a[2]=8。那么在进行两次组团训练之后，这两个士兵满级，于是sum_cost=sum_cost-a[2]。这样就能更新sum_cost了。然后继续比较组团训练和单独训练哪个花费更少，每次选择更少的即可。

代码部分

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5+10;
int p[N],c[N];
long long a[100*N]; //a[i]=k表示所有需要升级i次才满级的所有士兵升一级的总费用为k，这里样例中ci超过了10的6次方
//此题样例int a[100*N]也能过，我开long long是为了防止极端数据所有士兵每次升级都需要10的6次方，所有士兵都需要升级10的6次方次
int main()
{
    int n;
    long long s;
    cin >> n >> s;
    int max_t = 0;       //记录所有士兵中最大的单独训练次数
    long long ans = 0;   //最终消耗金币的数量  
    long long sum_cost = 0; //记录所有没有升级到满级的士兵一个一个升一级的总花销
    for(int i = 1;i<=n;i++)
    {
        cin>>p[i]>>c[i];
        sum_cost+=p[i];  //初始值就是所有士兵每次升级的花费总和
        a[c[i]]+=p[i];  //记录所有需要升c[i]级的士兵每次升级的花费总和
        max_t = max(max_t,c[i]);
    }

    for(int i = 1;i<=max_t;i++)   //遍历每一次升级，判断是选择组团好还是单独训练好
    {
        if(sum_cost>s)
        {
            ans+=s;  //团体训练更加划算
        }
        else
        {
            ans+=sum_cost;  //士兵单独训练更划算
        }
        //更新单独训练的花费，已经满级的士兵无须在单独训练
        sum_cost-=a[i]; //因为所有士兵已经升级了i级，那么所以i级为满级的士兵无须继续升级，下一次升级的花费无须计算这些士兵
    }

    cout<<ans<<endl;
    return 0;
}