首页 > 试题广场 >

护花使者

[编程题]护花使者
  • 热度指数：1079 时间限制：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}请为旺仔哥哥规划牵牛顺序，使 被毁坏花朵的总数 最小。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(2\leqq n\leqq 10^5\right)——奶牛数量。
\hspace{15pt}接下来 n 行，第 i 行输入两个整数 T_i,D_i\ \left(1\leqq T_i\leqq 2\times10^6;\ 1\leqq D_i\leqq 100\right)——第 i 头奶牛的距离与每分钟毁花的数量。


输出描述:
\hspace{15pt}输出一个整数，表示最优搬运顺序下被毁坏花朵的最小总数。
示例1

输入

6
3 1
2 5
2 3
3 2
4 1
1 6

输出

86

说明

\hspace{15pt}一种最优顺序为按 \{ 6,2,3,4,1,5\}（编号）依次搬运，可验证总毁花数为 86 且无法更小。

备注:
本题已于下方时间节点更新，请注意题解时效性：
1. 2026-01-18 修复了样例解释中的错误。
算法知识视频讲解
添加回答
随机名字666💭💡🎈头像 随机名字666💭💡🎈
羡慕旺仔哥哥
发表于 2026-01-18 09:37:08 回复(1)
驴主头像 驴主
为什么要去埃及拔草。
发表于 2026-01-18 20:33:39 回复(0)
aesadasewaew头像 aesadasewaew
挨什么草？
发表于 2026-01-18 17:46:07 回复(0)
DPsans头像 DPsans
样例“说明”的最优顺序有问题，应为<6, 2, 3, 4, 1, 5>。
发表于 2026-01-18 10:54:34 回复(1)
提交观点

问题信息

难度：
4条回答 49浏览

热门推荐

相关试题

护花使者

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号