Responsive image

问题 A: 保护花朵

问题 A: 保护花朵

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 48
[提交][状态][讨论版][命题人:]

题目描述

农夫约翰去砍柴，像往常一样留下了N头牛在吃草。当他回来时，他惊恐地发现那群牛正在他的花园里吃他美丽的花。为了尽量减少后续损失，FJ决定立即采取行动，将每头牛运回各自的谷仓。
每头牛i在距离它自己的谷仓Ti分钟的位置。此外，在等待运输时，每头牛每分钟会破坏Di朵花。无论他如何努力，FJ每次只能将一头牛运回牛棚。将奶牛i移动到它的谷仓需要2×Ti分钟(Ti到那里，Ti返回)。FJ从花圃出发，把牛送到牛棚，然后走回花丛，不需要额外的时间就可以到达下一头需要运输的牛那里。
编写一个程序来确定FJ应该以何种顺序捡起奶牛，从而使被破坏的花朵总数最小化。

输入描述

行1:一个整数N(2≤N≤10,000)
行2…N+1:每一行包含两个用空格隔开的整数，Ti和Di，它们描述了一头牛的特征。(1≤Ti≤2,000,000,1≤Di≤100)

输出描述

行1：被破坏的花朵总数最小值

样例输入

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

样例输出

86
[提交][状态]
ACM算法攻关部