Dotcpp  >  编程题库  >  啤酒厂选址
题目 2964:

啤酒厂选址

时间限制: 2s 内存限制: 192MB 提交: 64 解决: 14

题目描述

海上有一个岛,在环海边上建有一条环岛高速公路,沿着公路有n(5 < n < 10000)个居民点,假设每个居民点有一个编号,从0开始,按顺时针依次从小到大(即,0,1,…,n-1)编号。在岛上啤酒很受青睐。某啤酒企业计划在岛上投资建一个啤酒厂,并根据啤酒需求每天向居住点送啤酒。已知两个相邻的居民点的距离以及每个居住点每天的啤酒需求量(假设每个居住点每天不超过2000桶)。假定每单位长度的路程送一桶啤酒需要的费用恒定(为单位费用)。请问,选择哪一个居民点建啤酒厂,才能使每天送啤酒的费用最小(空车不计费用)。

输入格式

第一行:为居民点数目n。
后面为n行,每行为一个居民点的啤酒需求量以及按顺时针离下一个居民点的距离(均为整数,空格间隔),从编号为0的开始,按单增顺次给出。
注意:后面第n行对应于居民点(n-1)的啤酒需求量以及到编号为0的居民点距离。

输出格式

啤酒厂所在的居民点编号以及每天的运输费用,其间以逗号间隔。

样例输入

6
500 10
300 30
350 25
400 60
700 28
200 35

样例输出

0,94100

提示

零基础同学可以先学习视频课程,包含C/C++、Python、百练、蓝桥杯辅导、算法数据结构等课程,提供视频讲解以及配套习题,还有老师答疑,点击这里了解课程详情
标签