农夫约翰运奶牛问题解析

这道题目要求我们确定运输奶牛的顺序，使得在运输过程中被毁掉的花的总数最少。每头奶牛每分钟会毁掉一定数量的花，而运输每头奶牛需要一定时间，我们需要找到最优的运输顺序来最小化总损失。

解题思路

1. 问题分析：

   • 每头奶牛i在运输过程中会持续毁花，直到被运走
   • 运输奶牛i需要2×Ti分钟（去Ti分钟，回Ti分钟）
   • 约翰一次只能运输一头奶牛，运输顺序会影响总毁花量

2. 关键观察：

   • 假设我们有两头奶牛A和B，运输顺序会影响总损失
   • 设A的参数为(Ta, Da)，B的参数为(Tb, Db)
   • 若先运A再运B，总损失为：Da×(2×Ta) + Db×(2×Ta + 2×Tb)
   • 若先运B再运A，总损失为：Db×(2×Tb) + Da×(2×Tb + 2×Ta)
   • 比较两种顺序的损失差：Da×2Ta + Db×(2Ta+2Tb) - [Db×2Tb + Da×(2Tb+2Ta)] = 2TaDb - 2TbDa
   • 当TaDb < TbDa时，先运A更优，即运输顺序应满足Ta×Db < Tb×Da

3. 贪心策略：

   • 按照Ti×Dj < Tj×Di的规则排序奶牛
   • 即对于奶牛i和j，若Ti×Dj < Tj×Di，则i应在j之前运输

代码解析

下面是完整的C++代码，我将对关键部分进行解释：

#include <iostream>
#include <algorithm>
#include <stdio.h>

using namespace std;

const int N = 1e5;
struct Cow {
    int t, d;
    bool operator < (const Cow& a) const {
        return t * a.d < a.t * d;
    }
} cow[N];

int main()
{
    int n;
    
    while(~scanf("%d", &n)) {
        for(int i=0; i<n; i++)
            scanf("%d%d", &cow[i].t, &cow[i].d);
        
        sort(cow, cow + n);
        
        long long sumd = 0, sumt = 0;
        for(int i = 0; i<n; i++) {
            sumd += cow[i].d * sumt;
            sumt += cow[i].t * 2;
        }
        
        printf("%lld\n", sumd);
    }
    
    return 0;
}

算法步骤

1. 输入处理：

   • 读取奶牛数量N和每头奶牛的Ti（运输时间）、Di（每分钟毁花数）

2. 排序策略：

   • 定义奶牛结构体的比较函数，按照Ti×Dj < Tj×Di的规则排序
   • 这确保了最优的运输顺序

3. 计算总毁花量：

   • sumt记录已经用掉的总运输时间（包括往返）
   • 对于每头奶牛i，它在运输前的等待时间为sumt，毁花量为Di×sumt
   • sumd累加所有奶牛的毁花量
   • 每运输完一头奶牛，总运输时间增加2×Ti（往返时间）

时间复杂度分析

• 排序操作：O(N log N)，这是主要时间复杂度
• 遍历计算：O(N)
• 总体时间复杂度：O(N log N)，适用于N≤100,000的规模

空间复杂度分析

• 存储奶牛数据：O(N)
• 总体空间复杂度：O(N)

贪心策略证明

假设我们有两头奶牛A和B：

• 若先运A再运B，总毁花量为：Da×(2Ta) + Db×(2Ta+2Tb) = 2TaDa + 2TaDb + 2TbDb
• 若先运B再运A，总毁花量为：Db×(2Tb) + Da×(2Tb+2Ta) = 2TbDb + 2TbDa + 2TaDa
• 两者的差为：(2TaDa + 2TaDb + 2TbDb) - (2TbDb + 2TbDa + 2TaDa) = 2TaDb - 2TbDa
• 当TaDb < TbDa时，先运A的总毁花量更小
• 因此，按照Ti×Dj < Tj×Di的规则排序可以得到最优解

这种贪心策略确保了在每一步选择中，当前最优选择能导致全局最优解，适用于该问题的求解。