Protecting the Flowers POJ
最新推荐文章于 2022-02-14 16:43:03 发布

小宋想站起来 于 2019-08-06 21:27:47 发布
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
农夫约翰像往常一样去砍柴,留下N头(2≤N≤10万头)牛在吃草。当他回来时,他惊恐地发现那群牛正在他的花园里吃他美丽的花。为了将随后的损失降到最低,FJ决定立即采取行动,把每头牛运回自己的谷仓。
每头奶牛i所处的位置距离自己的牲口棚Ti分钟(1≤Ti≤2,000,000)。此外,在等待运输时,她每分钟破坏Di(1≤Di≤100)朵花。不管他怎么努力,FJ一次只能把一头牛运回她的谷仓。将奶牛i移到它的谷仓需要2×Ti分钟(Ti到那里,Ti返回)。FJ从花圃出发,把牛送到它的谷仓,然后走回花丛,不花额外的时间去找下一头需要运输的牛。
编写一个程序来确定FJ应该捡起奶牛的顺序,从而使被破坏的花朵总数最小化。
输入
第一行:一个整数N
行2 . .N+1:每一行包含两个空格分隔的整数,Ti和Di,它们描述了一头奶牛的特征
输出
第1行:一个整数,它是被破坏的花的最小数量
Sample Input
6 3 1 2 5 2 3 3 2 4 1 1 6
Sample Output
86
思路:贪心,应该送走破坏力较大的牛,假如只剩两头牛A,B,sumA是牛A的破坏力
sumB = eastB*timeA*2 sumA = eastA*timeB*2 两端同时除以timeA*timeB
sumB = eastB/timeB*2 sumA = eastA*timeA*2
所以题中 d/t 较大的牛破坏力大
#include<iostre
相关知识
flowers的意思
Flowers 花
Flowers and Plants Care
《干花与压花艺术》课程教学大纲.doc
《鲜花识别神器——flowers》
FLORAL SEASONAL FLOWERS是啥意思?
花卉 Flowers
605. Can Place Flowers
YY·Flowers自助插花店
Stig、Flowers、Photo、Keys、Branch、TOP、Usual
原文链接: Protecting the Flowers POJ https://m.huajiangbk.com/newsview389170.html
| 上一篇: 赛软件 * 比赛 = 软件比拼 | 下一篇: 花实球的台球比赛,规则是什么? |



