题目链接

护花使者

题目描述

有 头奶牛，每头奶牛 有两个属性：运送回牛棚并返回花园所需的往返时间 ，以及在等待期间每分钟毁坏花朵的数量 。每次只能运送一头奶牛。目标是规划一个运送顺序，使得所有奶牛毁坏的花朵总数最少。

解题思路

这是一个经典的排序贪心问题。我们的目标是最小化一个与顺序相关的成本总和。

首先，我们来建立成本函数。假设我们确定了一个运送顺序 。

  • 第一头奶牛 的等待时间为 。
  • 第二头奶牛 的等待时间为 。
  • 第三头奶牛 的等待时间为 。
  • ...
  • 第 头奶牛 的等待时间为 。

因此，第 头奶牛 毁坏的花朵数量为 。 所有奶牛毁坏的花朵总数 为：

邻项交换法证明

为了找到使 最小的顺序，我们可以使用邻项交换法来推导贪心准则。

假设在某个序列中，存在两头相邻的奶牛 和 ，其中 在 之后被运送。设运送 之前已经花费的时间为 。

  1. 原始顺序 (..., i, j, ...):

    • 的等待时间是 ，其毁坏的花朵数为 。
    • 的等待时间是 ，其毁坏的花朵数为 。
    • 这两头奶牛对总成本的贡献为 。

  2. 交换后 (..., j, i, ...):

    • 的等待时间是 ，其毁坏的花朵数为 。
    • 的等待时间是 ，其毁坏的花朵数为 。
    • 这两头奶牛对总成本的贡献为 。

为了使总成本最小，我们希望原始顺序 (i, j) 的成本小于交换后 (j, i) 的成本，即：

展开并消去两边都存在的项 和 ，我们得到：

这个不等式是奶牛 应该排在奶牛 前面的条件。为了避免使用浮点数除法，我们直接使用这个乘法形式。该条件等价于 。

结论

因此，最优的贪心策略是：将所有奶牛按照 的比值（即每分钟毁坏花朵数与运送往返时间的比值）进行降序排序。排序后，依次计算并累加每头奶牛造成的毁坏即可。

代码

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

using namespace std;

struct Cow {
    long long t, d;
};

bool compareCows(const Cow& a, const Cow& b) {
    // a在b前面 <==> d_a / t_a > d_b / t_b <==> d_a * t_b > d_b * t_a
    return a.d * b.t > b.d * a.t;
}

int main() {
    int n;
    cin >> n;

    vector<Cow> cows(n);
    for (int i = 0; i < n; ++i) {
        long long single_trip_time;
        cin >> single_trip_time >> cows[i].d;
        cows[i].t = 2 * single_trip_time;
    }

    sort(cows.begin(), cows.end(), compareCows);

    long long total_destroyed = 0;
    long long time_elapsed = 0;
    
    for (int i = 0; i < n; ++i) {
        total_destroyed += cows[i].d * time_elapsed;
        time_elapsed += cows[i].t;
    }

    cout << total_destroyed << endl;

    return 0;
}

import java.util.*;

public class Main {
    static class Cow {
        long t, d;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Cow[] cows = new Cow[n];
        for (int i = 0; i < n; i++) {
            cows[i] = new Cow();
            long singleTripTime = sc.nextLong();
            cows[i].t = 2 * singleTripTime;
            cows[i].d = sc.nextLong();
        }

        Arrays.sort(cows, (a, b) -> {
            // d_a / t_a > d_b / t_b  <==> d_a * t_b > d_b * t_a
            long val = b.d * a.t - a.d * b.t;
            if (val > 0) return 1;
            if (val < 0) return -1;
            return 0;
        });

        long totalDestroyed = 0;
        long timeElapsed = 0;
        
        for (int i = 0; i < n; i++) {
            totalDestroyed += cows[i].d * timeElapsed;
            timeElapsed += cows[i].t;
        }

        System.out.println(totalDestroyed);
    }
}

import sys
from functools import cmp_to_key

class Cow:
    def __init__(self, t, d):
        self.t = t
        self.d = d

def compare_cows(a, b):
    # a in front of b <==> a.d / a.t > b.d / b.t <==> a.d * b.t > b.d * a.t
    val = a.d * b.t - b.d * a.t
    if val > 0:
        return -1
    elif val < 0:
        return 1
    else:
        return 0

def solve():
    n = int(input())
    cows = []
    for _ in range(n):
        single_trip_time, d = map(int, input().split())
        cows.append(Cow(2 * single_trip_time, d))
    
    cows.sort(key=cmp_to_key(compare_cows))

    total_destroyed = 0
    time_elapsed = 0
    
    for cow in cows:
        total_destroyed += cow.d * time_elapsed
        time_elapsed += cow.t
        
    print(total_destroyed)

solve()

算法及复杂度

  • 算法：贪心算法
  • 时间复杂度：
    • 主要开销在于对 头奶牛进行排序。
  • 空间复杂度：
    • 用于存储 头奶牛的信息。