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

解题思路:
每次都让全部士兵开始训练让训练次数少的在前，并判断组团和单独那个更优即可
注意事项:

参考代码:

#include"bits/stdc++.h"
using namespace std;
#define ll long long
#define endl '\n'
const ll N=1e5+5;
struct node{
    ll p,c;
}a[N];
ll n,s,kkk;
ll sum;
bool cmp(node a,node b){
    return a.c<b.c;//按训练次数升序
}
int main(){
    cin>>n>>s;
    for(ll i=1;i<=n;i++){
       cin>>a[i].p>>a[i].c;
       sum+=a[i].p;//sum为总金币成本
    }
    sort(a+1,a+1+n,cmp);
    ll ans=0;//ans为每名士兵已训练次数
    for(ll i=1;i<=n;i++){
       a[i].c-=ans;//训练次数减去已训练次数
       if(a[i].c!=0){//训练次数不为0，及还有训练次数
          if(s<=sum){//组团训练更优
             kkk+=a[i].c*s;
          }
          else kkk+=a[i].c*sum;//单独训练更优
       }
       ans+=a[i].c;
       sum-=a[i].p;//减去训练完的士兵的金币成本
    }
    cout<<kkk<<endl;
    return 0;
}