首页 > 试题广场 >

护花使者

[编程题]护花使者

热度指数：1154 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\hspace{15pt}$ 旺仔哥哥打算去埃及拔草，留下他的 $n$ 头奶牛在草地上吃草。从埃及拔草回来后，旺仔哥哥震惊地发现奶牛们闯入了他的花园并开始啃食鲜花，旺仔哥哥必须尽快将每头奶牛送回各自的牛棚。
$\hspace{15pt}$ 第 $i$ 头奶牛距离其牛棚需要 $T_i$ 分钟步行（但是因为旺仔哥哥把奶牛送回去之后还要走回来，所以把一头奶牛送回牛棚并回到花园实际上会消耗 $2 \cdot T_i$ 分钟）。等待运送期间，这头奶牛每分钟会毁坏 $D_i$ 朵花。
$\hspace{15pt}$ 旺仔哥哥一次只能牵走一头奶牛，且每次都从花园出发，将奶牛送回牛棚后立即返回花园，立刻牵走另一头奶牛。
$\hspace{15pt}$ 请为旺仔哥哥规划牵牛顺序，使 被毁坏花朵的总数 最小。

输入描述:

第一行输入一个整数 ——奶牛数量。
接下来  行，第  行输入两个整数 ——第  头奶牛的距离与每分钟毁花的数量。

输出描述:

输出一个整数，表示最优搬运顺序下被毁坏花朵的最小总数。

示例1

输入

输出

说明

一种最优顺序为按 （编号）依次搬运，可验证总毁花数为  且无法更小。

备注:

本题已于下方时间节点更新，请注意题解时效性：
1. 2026-01-18 修复了样例解释中的错误。

算法知识视频讲解

丨阿伟丨

发表于 2025-09-10 10:15:45

题目链接护花使者题目描述有头奶牛，每头奶牛有两个属性：运送回牛棚并返回花园所需的往返时间，以及在等待期间每分钟毁坏花朵的数量。每次只能运送一头奶牛。目标是规划一个运送顺序，使得所有奶牛毁坏的花朵总数最少。解题思路这是一个经典的排序贪心问题。我们的目标是最小化一个与顺序相关的成本展开全文

Minazuki_Hotaru

发表于 2026-01-18 06:13:31

贪心如果一头牛的破坏力越强，迁到牛棚的时间越少，我们去迁走它那么损失越小，我们按去排序，防止被卡精度，我们对两个牛排序的时候去比较与，这边贴代码 /* ## ## ####### ######## ### ######## ## ## ## ## 展开全文

BaiJay

发表于 2026-01-18 10:11:56

奶牛运送最小总损失问题 - 核心思路一、核心算法：贪心算法（局部最优推导全局最优）贪心算法的核心是找到局部最优判断规则，通过每一步的局部最优选择，最终得到全局最优解，本问题的核心就是推导奶牛运送的最优排序规则。二、关键：两两奶牛对比推导排序规则假设仅有两头奶牛 A(t1, d1) 和 B( 展开全文

未完成秋天

发表于 2026-01-18 00:43:37

贪心中很重要且典型的一种策略：交换论证。结论：存在最优策略序列，使得毁坏花朵总数最少，当且仅当：考虑这个序列中的任意一对相邻点 a，b，若 a 在 b 之前送走，均有 a.time*b.harm<=b.time*a.harm.证明：假设存在一种策略序列，存在相邻点 a b 使得 a.time* 展开全文

软件25_4刘卓生

发表于 2026-01-18 13:19:00

本题是一个侧重于数学证明的排序贪心问题，调度优化问题核心思路核心观察这是一个经典的调度优化问题。关键在于：先送哪头奶牛会影响后续奶牛的等待时间。如果先送奶牛 A 再送奶牛 B：奶牛 A 的等待时间 = 0（立即被送走）奶牛 B 的等待时间 = 总毁花数 = 如果先送奶展开全文

Kato_Shoko

发表于 2026-01-18 13:46:05

一种比较常见的排序方式，详情可看：【1月18日牛客每日一题】 #include <bits/stdc++.h> #define il inline #define double long double using namespace std; using ll = long long; 展开全文

此在Dasein

发表于 2026-01-18 06:33:24

本问题是一个经典的组合优化问题，具体属于单机调度问题（Single Machine Scheduling）的变种。我们需要确定一个处理任务（运送奶牛）的线性顺序，使得累积的“惩罚成本”（花朵被毁坏的总数）最小。贪心算法由于任意两头奶牛的交换只影响它们彼此之间的相对成本贡献，而不改变它们之前或之后展开全文

YunBaichuan

发表于 2026-01-18 09:36:40

参考及具体证明：https://blog.nowcoder.net/n/b5b3c86f177943bf9173333de3c027eb 思路：贪心，猜结论。我们要让损失的花朵最少，那么很容易想到贪心策略：越早运输损失大的牛越好，那该如何衡量损失大？应该用进行衡量，如果比值越大，那么我们要优先运输这展开全文