题解 | #护花使者#

本题是一个侧重于数学证明的排序贪心问题，调度优化问题

核心思路

核心观察

这是一个经典的调度优化问题。关键在于：先送哪头奶牛会影响后续奶牛的等待时间。

• 如果先送奶牛 A 再送奶牛 B：

  • 奶牛 A 的等待时间 = 0（立即被送走）
  • 奶牛 B 的等待时间 =
  • 总毁花数 =

• 如果先送奶牛 B 再送奶牛 A：

  • 总毁花数 =

要选择更优的顺序，我们需要比较： 2⋅TA⋅DBvs2⋅TB⋅DA

消去常数 2，得到比较条件：

即：当 时，应该先送 A

等价于排序规则：

但为了避免浮点数精度问题，我们使用交叉相乘的比较方式。

算法步骤

1. 预处理：将每头奶牛的 乘以 2（因为往返时间）
2. 排序：按照比较规则 a.T * b.D < b.T * a.D 对奶牛排序
   • 即：如果 a.T * b.D < b.T * a.D，则 a 应该排在 b 前面
3. 计算答案：
   • 维护已花费的总时间 total_time
   • 按排序后的顺序处理每头奶牛：
     • 这头奶牛的等待时间 = total_time
     • 毁花数贡献 = total_time * D_i
     • 更新 total_time += 2 * T_i

注：由于 最大为 ， 最大为 100， 最大为 ，总毁花数可能达到 级别，需要使用 long long。

正确性分析

• 贪心选择性质：任意相邻两头奶牛的最优顺序都满足上述比较规则，因此全局最优解可以通过局部最优选择得到。
• 交换论证：如果存在一个最优解中相邻两头奶牛不满足我们的排序规则，那么交换它们会得到更优或相等的结果，矛盾。
• 边界处理：第一头奶牛等待时间为 0，符合实际情况。

复杂度分析

• 时间复杂度：，主要消耗在排序
• 空间复杂度：，存储奶牛信息

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct cow{
    int time,d;
};
bool cmp(cow& a,cow&b){
    return a.d*b.time>b.d*a.time;
}
signed main() {
    int n;cin>>n;
    vector<cow>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i].time>>v[i].d;
        v[i].time*=2;
    }
    sort(v.begin(),v.end(),cmp);
    int total=0,ans=0;//目前累加的时间，答案
    for(int i=0;i<n;i++){
        ans+=total*v[i].d;
        total+=v[i].time;//当前奶牛等待的时间
    }
    cout<<ans;
}