速度更快，思路更简单的贪心算法

解题思路:速度更快，思路更简单的贪心算法

注意事项:

参考代码:

#include<iostream>

#include<algorithm>

#include<vector>

using namespace std;

struct Solider {

    long long int cos;

    long long int num;

};

vector<Solider>So;

void Caculate(long long int n,long long  int s)

{

    long long int end = 0;

    long long int m = n;

   long long  int sum = 0;  // 必须从0开始！！！！！！

    long long int max = 0;

    while (true)

    { 

            n--;

            if (n == -1)

            {

                n++;

                break;  // 先判断，防止越界！！！

            }

        if (sum + So[n].cos <= s) {

            sum += So[n].cos;

        }

        else {

            n++; // 退回到正确位置

            break;

        }

    }

    //cout << "n的值为" << n << endl;

    for (int i = 0; i < n; i++)

    {

        if (So[i].num > max)

        {

            max = So[i].num;

        }

    }

    //cout << "最多能一起训练" << max << endl;

    if (n == 0)

    {

        for (int i = 0; i < m; i++)

        {

            end = end + So[i].cos * (So[i].num);

        }

        cout << end;

    }

    else {

        for (int i = m - n; i < m; i++)

        {

           // cout << "当前的总花费" << end<<" ";

          //  cout << "需要单独训练的士兵号" << i <<"";

            if (So[i].cos * (So[i].num - max) > 0)

            {

                end = end + So[i].cos * (So[i].num - max);

            }

           // cout << So[i].cos * (So[i].num - max)<<" ";

           // cout << "此时的花费" << end << endl;

        }

      // cout << "单独训练的费用" << end << endl;

        end = end + max * s;

        cout << end;

    }

}

int cmp(Solider a, Solider b)

{

    return a.num < b.num;

}

int main()

{

    long long int n, s;

    cin >> n >> s;

    for (int i = 0; i < n; i++)

    {

       long long int a, b;

        cin >> a >> b;

        Solider t;

        t.cos = a;

        t.num = b;

        So.push_back(t);

    }

    sort(So.begin(), So.end(), cmp);

    Caculate(n, s);

}