题解 | 护花使者

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll N=1e5+5;

// 定义奶牛结构体：存储每头奶牛的往返时间T（单程T分钟，往返2*T）、每分钟毁花数D
struct caw{
    ll T;  // 运输该奶牛单程所需时间（分钟）
    ll D;  // 该奶牛每分钟毁掉的花朵数量
};

caw a[N];  // 存储所有奶牛的信息

int main() {
    // 关闭cin/cout同步，加速输入输出（处理大数据量时必要）
    ios::sync_with_stdio(0),cin.tie(0);
    
    ll n;
    cin>>n;  // 读取奶牛总数
    
    // 步骤1：输入每头奶牛的T和D
    for(ll i=1;i<=n;i++){
        cin>>a[i].T>>a[i].D;
    }
    
    // 步骤2：贪心排序（核心）
    // 排序规则：a.T*b.D < b.T*a.D → a排在b前面
    // 规则推导：优先运输"时间×对方毁花数"更小的奶牛，总毁花量最小
    // 本质是比较两头牛i/j：若T_i*D_j < T_j*D_i，则先运i更优
    sort(a+1,a+n+1,[](caw a,caw b){
        return a.T*b.D<b.T*a.D;
    });
    
    // 步骤3：初始化累计时间和总毁花数
    ll t=2*a[1].T;  // 第一头奶牛的往返时间（它被运走后，后续奶牛开始累计等待时间）
    ll ans=0;       // 存储所有奶牛毁掉的花朵总数
    
    // 步骤4：遍历计算每头奶牛的毁花量并累加
    // 第i头奶牛的毁花量 = 它的D × 前面所有奶牛的往返时间总和（它的等待时间）
    for(ll i=2;i<=n;i++){
        ans+=a[i].D*t;  // 累加当前奶牛的毁花量
        t+=2*a[i].T;    // 更新累计往返时间（加上当前奶牛的往返时间）
    }
    
    // 步骤5：输出总毁花数
    cout<<ans;
    return 0;
}