自动搬运

查看原文

来自洛谷，原作者为

	ydclyq 不想成为任何人的一时之需

搬运于2025-08-24 22:41:53，当前版本为作者最后更新于2023-02-24 12:06:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

本题的基本思路是贪心。

对于任意一种顺序，

如果我们交换相邻的学生 $i,i+1$, 在交换前这两个同学的时刻总和是：

$(s_i+a_i)+(s_i+a_i+e_i+s_{i+1}+a_{i+1})$

交换后这两个同学的时刻总和是：

$(s_{i+1}+a_{i+1})+(s_{i+1}+a_{i+1}+e_{i+1}+s_i+a_i)$

显然这两个同学的交换顺序不会引起其他学生发消息的时刻变化。

我们不妨令未交换之前时刻总和更小，对式子进行化简：

$s_i+a_i+e_i<s_{i+1}+a_{i+1}+e_{i+1}$

那么说明 $s_i,a_i,e_i$ 加和越小，放在前面的的话答案越小。

于是我们便找到了排序方法。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int T = 1;
int n;
struct D{
    int s,a,e;
    bool operator < (const D&B) const{
        return s+a+e<B.s+B.a+B.e;
    }
}h[1005];

void solve(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>h[i].s>>h[i].a>>h[i].e;
    }
    sort(h+1,h+n+1);
    ll ans=0,now=0;
    for(int i=1;i<=n;i++){
        now+=h[i].s+h[i].a;
        ans+=now;
        now+=h[i].e;
    }
    cout<<ans;
}

int main(){
    //cin >> T;
    while (T--) solve();
    return 0;
}