| 题目名称 | 243. [POI 2000] 啤酒厂建造 |
|---|---|
| 输入输出 | bro.in/out |
| 难度等级 | ★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 17 |
| 题目来源 |
 BYVoid
于2008-12-21加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：36， 提交：118， 通过率：30.51% | ||||
 佾 |
100 | 0.000 s | 0.00 MiB | C++ |
 TA |
100 | 0.013 s | 0.47 MiB | C++ |
 pztl |
100 | 0.016 s | 0.39 MiB | C++ |
|
TA |
100 | 0.018 s | 0.77 MiB | C++ |
 蒟蒻mhr |
100 | 0.024 s | 0.87 MiB | C++ |
 kaaala |
100 | 0.028 s | 0.34 MiB | C++ |
|
TA |
100 | 0.029 s | 0.47 MiB | C++ |
 BYVoid |
100 | 0.049 s | 0.33 MiB | C++ |
 Pom |
100 | 0.053 s | 0.49 MiB | C++ |
 Pierre |
100 | 0.066 s | 30.83 MiB | C++ |
| 关于 啤酒厂建造 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
定义 longlong 居然会慢！！涨姿势了！！
 浮生随想
2016-11-13 07:46
2楼
| ||||
|
我就知道O(n^2)的算法可以过
| ||||
open the window【题目描述】
Abstinence岛的居民非常喜欢喝alkoholfree啤酒。虽然到目前为止这种啤酒还是从波兰进口的，但今年他们要在岛上的某一城市建一 啤酒厂。所有城市都位于海岸边，彼此之间通过一条环绕全岛的高速公路联接。啤酒投资商搜集了一些啤酒需求量的信息，譬如每个城市的日啤酒消费量为多少件， 任意俩城市的距离等。一件啤酒每英里的运输费用是一泰勒，因而，将适当件数的啤酒从啤酒厂运往各个城市时，每天的费用将会是很大一笔数目。问题的关键在于 啤酒厂的位置。投资商想找到一个使得日花费量为最小的城市来建造啤酒厂。
【输入格式】
第一行的整数N表示城市的个数，5<=N<=10000(我们假定城市都是沿高速公路编号，相邻的城市编号也紧接。城市一与城 市N相邻）。
接下来的N行每行为俩个用单个空格隔开的非负数。第I+1行的数字Z（I）与D（I）分别表示为城市I的啤酒需求量和从城市I沿高速公路到下 一城市的距离（用英里做度量）。
公路的总长不超过1000000英里。每一城市日啤酒需求量不大于1000件。
【输出格式】
一行一个整数，此整数应为日运输费用的最小值。
【样例输入】
6 1 2 2 3 1 2 5 2 1 10 2 3
【样例输出】
41