P8732 [蓝桥杯 2020 国 ABC] 答疑

ydclyq · 2023-02-24 12:06:17 · 题解

题目链接

本题的基本思路是贪心。

对于任意一种顺序，

如果我们交换相邻的学生 i,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;
}