文章

答疑(2020国赛)

答疑1.png答疑2.png

按照每个人时间总和从小到大排序得到的顺序就是最优解 证明见下

#include<bits/stdc++.h>
using namespace std;
struct stu{
    long long int x;
    long long int y;
};
long long int cmp(stu t1,stu t2){
    return t1.x+t1.y<t2.x+t2.y;
}
int main()
{
    long long int n,sum=0,i,p,q,ans=0;
    cin>>n;
    struct stu a[3000];
    for(i=0;i<n;i++){
        cin>>p>>q>>a[i].y;
        a[i].x=p+q;
    }
    sort(a,a+n,cmp);
    sum=a[0].x;
    ans=a[0].x;
    for(i=1;i<n;i++){
        ans=ans+a[i-1].y+a[i].x;
        sum=sum+ans;
    }
    cout<<sum<<endl;
    return 0;
 } 

原题链接

https://www.lanqiao.cn/problems/1025/learning/

License:  CC BY 4.0