蓝桥杯2020年第十一届国赛真题-答疑 C++ 排序 贪心

解题思路:在前面都选择花费总时间最少的 最后的答案一定是花费时间最少的

注意事项:记得开 long long

参考代码:

#include<bits/stdc++.h>

#define int long long

using namespace std;

struct st{

    int s,a,e,sum;

}st[1010];

int n,ans;

bool cmp(const struct st& p1,const struct st& p2){//从小到大

    return p1.sum<p2.sum;

}

signed main()

{   

    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    cin>>n;

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

        cin>>st[i].s>>st[i].a>>st[i].e;

        st[i].sum=st[i].s+st[i].a+st[i].e;

    }

    sort(st,st+n,cmp);

    int temp=0;

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

        temp+=(st[i].s+st[i].a);

        ans+=temp;

        temp+=st[i].e;

        //cout<<temp<<" ";

    }

    cout<<ans<<endl;

    return 0;

}