| 题目名称 | 180. [USACO Open07] 保护花朵 |
|---|---|
| 输入输出 | flowers.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 BYVoid
于2008-10-11加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：98， 提交：171， 通过率：57.31% | ||||
 Hakurou! |
100 | 0.001 s | 0.00 MiB | C++ |
 LCWhiStLe |
100 | 0.008 s | 0.29 MiB | C++ |
 Frank |
100 | 0.040 s | 1.66 MiB | C++ |
 KEVI_ |
100 | 0.041 s | 1.81 MiB | C++ |
 1020 |
100 | 0.043 s | 0.78 MiB | C++ |
 QWERTIer |
100 | 0.043 s | 1.05 MiB | C++ |
 雪，青天 |
100 | 0.057 s | 1.84 MiB | Pascal |
 宝宝宝 |
100 | 0.058 s | 1.69 MiB | Pascal |
 Twist Fate |
100 | 0.058 s | 1.69 MiB | Pascal |
 Ying |
100 | 0.058 s | 4.74 MiB | Pascal |
| 关于 保护花朵 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
貌似不用什么优化..
Hakurou!
2016-09-04 16:11
7楼
| ||||
|
需要unsigned long long和一个小优化qaq
| ||||
|
约翰留下了 N 只奶牛呆在家里，自顾自地去干活了，这是非常失策的。他还在的时候，奶牛像往常一样悠闲地在牧场里吃草。可是当他回来的时候，他看到了一幕惨剧：他的奶牛跑进了他的花园，正在啃食他精心培育的花朵！约翰要立即采取行动，挨个把它们全部关回牛棚。约翰牵走第 i 头奶牛需要 Ti 分钟，因为要算来回时间，所以他实际需要2 · Ti 分钟。第 i 头奶牛如果还在花园里逍遥，每分钟会啃食 Di 朵鲜花。但只要约翰抓住了它，开始牵走它的那刻开始，就没法吃花了。请帮助约翰写一个程序来决定押送奶牛的顺序，使得花朵损失的数量最小。
 Lovelove_boii
2016-07-03 16:16
5楼
| ||||
|
有n头牛在糟蹋庄稼。把第i头牛牵回家需要ti分钟。第i头牛每分钟会摧毁di的庄稼。每次只能牵一头牛走。问怎么牵使损失最少。
思路： 考虑a,b两牛。先牵a牛和b牛的损失分别为。2*d[b]*t[a]，2*d[a]*t[b]。设先牵a更优。2*d[b]*t[a]<2*d[a]*t[b]. 所以根据优先级排序然后依次牵就是最优的选择。  风间净无尘
2016-07-03 16:14
4楼
| ||||
|
农民约翰去砍柴左N（2≤N≤100000）牛吃的草，像往常一样。当他回来的时候，他发现他的恐惧，牛的集群在他的花园里吃他美丽的花。为了减少后续伤害，FJ决定立即采取行动和运输每头牛回到自己的谷仓。
我是在每头奶牛，Ti分钟位置（1≤钛≤2000000）远离自己的谷仓。此外，在等待运输，她破坏了DI（1≤迪≤花每分钟100）。不管他如何努力，FJ一次只能回到谷仓运输一头奶牛。移动的牛我对它的谷仓需要2×Ti分钟（TI去TI返回）。FJ在花片开始，运牛的谷仓，然后走回花，以没有多余的时间去下一头奶牛，需要运输。 写一个程序来确定顺序，FJ应该拿起牛因此总花朵数破坏最小化。输入 1号线：一个单一的整数n 线路2：N + 1：每行包含两个整数Ti和迪，描述一个牛的特点 输出 1号线：一个整数，是被破坏的花的最小数量  月落九天
2016-07-03 16:13
3楼
| ||||
|
先贪的速度，10分
后贪的时间，10分 样例都可以说的过去啊…… 但是，[贪心算法]无误，“高级”贪心，保证有输出数据大于2^31-1（C++中，int型不够；Pascal中，longint型不够） 用数据算出每头牛的“既方便处理又危险”指数，“既方便处理又危险”指数高的优先迁走。（或叫，小代价得大利益指数） 虽然后来知道了这样，求高人证明啊 | ||||
|
不错
 zqzas
2008-10-12 16:19
1楼
| ||||
Mealy
Truth.Cirno【题目描述】
FJ去砍柴了，留下N(2<=n<=100,000)头奶牛在牧场里像往常一样吃草。当他回来的时候，他惊恐的
发现牛们组队去他的花园里吃花了。为了将FJ花园的损失最小化，FJ决定采取快速的行动——把每头奶牛赶回她们自己的牛棚里。每头奶牛i所在的位置到她们
自己的牛棚要花费Ti(1<=Ti<=2,000,000)分钟，每头奶牛在花园中每分钟都会吃掉Di(1<=Di<=100)
朵花。
贴士：
1.FJ每次只能赶一头牛回牛棚。
2.因为FJ要一来一回，所以说他每赶一头牛回牛棚要花费2*Ti分钟。
3.FJ从花园中出发赶一头奶牛回牛棚，再从牛棚走到花园。
4.因为FJ会瞬移，所以说到花园之后不需要花多余的时间赶到下一头牛所在的地方。
求一个合理的顺序使FJ到花园损失的花朵数最小。
【输入格式】
第1行：一个单独的整数N。
第2~N+1行：两个由空格分开的整数，分别描述第i头奶牛的Ti和Di。
【输出格式】
第1行：一个单独的整数，表示FJ损失的花的最小数目。
【输入样例】
6 3 1 2 5 2 3 3 2 4 1 1 6
【输出样例】
86
【样例解释】
FJ赶牛的顺序是6-2-3-4-1-5，当他赶牛6时他损失了24朵花，当他赶牛2时他损失了28朵花，当他赶牛3时他损失了16朵花，
当他赶牛4时他损失了12朵花，当他赶牛1时他损失了6朵花，当他赶牛5时他损失了0朵花。24+28+16+12+6+0=86。
译：KZFFFFFFFF