题解 | #护花使者#

本问题是一个经典的组合优化问题，具体属于单机调度问题（Single Machine Scheduling）的变种。我们需要确定一个处理任务（运送奶牛）的线性顺序，使得累积的“惩罚成本”（花朵被毁坏的总数）最小。

贪心算法

由于任意两头奶牛的交换只影响它们彼此之间的相对成本贡献，而不改变它们之前或之后奶牛的等待时间，该问题满足局部最优解即全局最优解的性质。我们可以通过邻项交换法 (Exchange Argument) 来推导出最优排序规则。

贪心策略

假设最优序列中有两头相邻的奶牛：奶牛 A 和 奶牛 B。 我们比较两种顺序的局部成本差异（假设这两头奶牛之前的总耗时和之后的总及破坏率是固定的，可以抵消）：

1. 顺序 （先运 A，后运 B）：

   • 运送 A 期间，B 仍在花园中等待。
   • B 造成的破坏 = (运送 A 的往返时间) (B 的破坏率)
   • 

2. 顺序 （先运 B，后运 A）：

   • 运送 B 期间，A 仍在花园中等待。
   • A 造成的破坏 = (运送 B 的往返时间) (A 的破坏率)
   • 

3. 最优条件判断： 如果顺序 优于 ，则必须满足： 消除常数 2 并移项（假设 均为正数）： 或者写成比率形式（便于直观理解）：

结论

为了使总破坏数最小，我们应该优先运送 时间短 ( 小) 且 破坏力大 ( 大) 的奶牛。 排序规则：按照 的比值从小到大排序；如果为了避免浮点数精度问题，应使用乘法形式判断：。

复杂度分析

时间复杂度

1. 排序：对 头奶牛进行基于贪心规则的排序。
   • 复杂度：
2. 成本计算：遍历一次排序后的数组，累加破坏值。
   • 复杂度：
3. 总时间复杂度：。
   • 对于 ，这在标准的1秒时间限制内非常安全。

空间复杂度

1. 存储：需要存储 组 对。
   • 复杂度：
2. 总空间复杂度：。

代码实现

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> T(n);
    vector<int> D(n);
    long long sumD = 0LL;
    for (int i = 0; i < n; i++) {
        cin >> T[i] >> D[i];
        sumD += (long long)D[i];
    }

    vector<int> ids(n);
    iota(ids.begin(), ids.end(), 0);
    sort(ids.begin(), ids.end(), [&](const int i, const int j) {
        return T[i] * D[j] < T[j] * D[i];
    });

    long long total = 0LL;
    for (int i = 0; i < n; i++) {
        int idx = ids[i];
        sumD -= D[idx];
        total += 2LL * (long long)T[idx] * sumD;
    }

    cout << total << endl;
}