A7362 | [USACO07JAN] Protecting the Flowers S
来源USACO
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
有 $n$ 头奶牛跑到 FJ 的花园里去吃花儿了。
第 $i$ 头奶牛在距离牛圈 $T_i$ 的地方吃花，这里的 $T_i$ 表示 FJ 从牛圈到这头奶牛所在位置需要 $T_i$ 分钟。
第 $i$ 头奶牛每分钟会吃掉 $D_i$ 朵花。
FJ 现在要将这些奶牛赶回牛圈，但是他每次只能赶一头牛回去。
如果赶第 $i$ 头牛回牛圈，来回总共需要 $2\times T_i$ 分钟。
在这段时间内，其它还没有被赶回牛圈的奶牛会继续吃花，速度保持不变。
正在被赶回牛圈的奶牛不会继续吃花。
请你求出，在最优安排下，所有奶牛一共吃掉的花的最小数量。
第 $i$ 头奶牛在距离牛圈 $T_i$ 的地方吃花，这里的 $T_i$ 表示 FJ 从牛圈到这头奶牛所在位置需要 $T_i$ 分钟。
第 $i$ 头奶牛每分钟会吃掉 $D_i$ 朵花。
FJ 现在要将这些奶牛赶回牛圈，但是他每次只能赶一头牛回去。
如果赶第 $i$ 头牛回牛圈，来回总共需要 $2\times T_i$ 分钟。
在这段时间内，其它还没有被赶回牛圈的奶牛会继续吃花，速度保持不变。
正在被赶回牛圈的奶牛不会继续吃花。
请你求出，在最优安排下，所有奶牛一共吃掉的花的最小数量。
输入格式
第一行一个正整数 $n$。
接下来 $n$ 行，每行两个正整数 $T_i,D_i$。
接下来 $n$ 行，每行两个正整数 $T_i,D_i$。
输出格式
输出一行一个整数，表示答案。
输入输出样例
输入 #1
6 3 1 2 5 2 3 3 2 4 1 1 6
输出 #1
86
## 样例解释
最优策略是按照 $6\to 2\to 3\to 4\to 1\to 5$ 的顺序把牛赶回牛圈。
## 数据范围
对于 $100\%$ 的数据：
$1\le n\le 10^5$
$1\le T_i\le 2\times 10^6$
$1\le D_i\le 100$
最优策略是按照 $6\to 2\to 3\to 4\to 1\to 5$ 的顺序把牛赶回牛圈。
## 数据范围
对于 $100\%$ 的数据：
$1\le n\le 10^5$
$1\le T_i\le 2\times 10^6$
$1\le D_i\le 100$
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？