题目信息

平台：牛客
题目：护花使者
难度：中等
题目链接：护花使者

题目描述

有 n 个目标，每个目标 i 需要往返时间 2*T[i] 才能处理完；在它仍未处理期间，会以速率 D[i] 持续造成“伤害/代价”。需要选择处理顺序，使得累计伤害总和最小。

初步思路

假设按某一顺序处理，处理一个目标需要的时间会让“剩余目标”的伤害继续累计。
处理顺序只影响“每个目标被推迟的时间”，因此是一个经典的排序优化问题。

算法分析

核心：把每个目标看作“处理时间 2*T[i]”与“权重 D[i]”的调度问题，用排序规则最小化加权等待。
技巧：按 T[i]/D[i] 升序排序；用交叉相乘避免浮点误差。
时间复杂度：O(n log n)
空间复杂度：O(n)

正确性简述
考虑两个目标 i、j 的相对顺序。若 i 在前，则贡献为 2*T[i]D[j]；若 j 在前，则贡献为 2T[j]*D[i]。为了使前者不大于后者，需要 T[i]/D[i] <= T[j]/D[j]，因此按该比值升序排序可得到最优顺序（局部交换最优性）。

代码实现（C++）

#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>

using namespace std;

int main() {
    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 ans = 0LL;
    for (int i = 0; i < n; ++i) {
        int idx = ids[i];
        sumD -= D[idx];
        ans += 2LL * (long long)T[idx] * sumD;
    }

    cout << ans << endl;
}

测试用例

输入	输出	说明
n=2; (T,D)=(1,10),(3,1)	2	先做(1,10)：总伤害=211=2
n=2; (T,D)=(3,10),(1,1)	6	先做(1,1)：总伤害=2110=20，排序避免更大值
n=3; (2,3),(1,5),(3,2)	22	按 T/D 升序排序验证

总结与反思

这类题常见于“最小化加权等待”的排序模型，关键在于相对顺序的交换论证。
处理比值排序时建议用交叉相乘规避精度问题。

TK的小站

2026-01-18-牛客每日一题-护花使者