UC知道明天比赛了,问道noip题目~~
来源：百度知道 编辑：UC知道 时间：2024/05/10 05:54:03
啤酒厂建造(bro)
[题目描述]
Abstinence岛的居民非常喜欢喝alkoholfree啤酒。虽然到目前为止这种啤酒还是从波兰进口的，但今年他们要在岛上的某一城市建一啤酒厂。所有城市都位于海岸边，彼此之间通过一条环绕全岛的高速公路联接。啤酒投资商搜集了一些啤酒需求量的信息，譬如每个城市的日啤酒消费量为多少件，任意俩城市的距离等。一件啤酒每英里的运输费用是一泰勒（注：旧德币），因而，将适当件数的啤酒从啤酒厂运往各个城市时，每天的费用将会是很大一笔数目。问题的关键在于啤酒厂的位置。投资商想找到一个使得日花费量为最小的城市来建造啤酒厂。
编写程序：
读入城市的个数，任意两城市的距离，以及他们的日啤酒消费量；
计算日运输费用的最小值。
[输入格式]
第一行的整数N表示城市的个数，(我们假定城市都是沿高速公路编号，相邻的城市编号也紧接。城市一与城市N相邻)。接下来的N行每行为俩个用单个空格隔开的非负数。第I+1行的数字Z（I）与D（I）分别表示为城市I的啤酒需求量和从城市I沿高速公路到下一城市的距离（用英里做度量）。
[输出格式]
你的程序将在第一行且只在这一行写入一整数，此整数应为日运输费用的最小值。
[样例输入]
6
1 2
2 3
1 2
5 2
1 10
2 3
[样例输出]
41
[数据范围]
100%的数据, 5<=N<=10000,
公路的总长不超过1000000英里,
每一城市日啤酒需求量不大于1000件。
主要在与数据量为10000,要求1s内出解
program pro(input,output);
var
a,b:array[1..10001] of word;
min,s,temp1,temp2:extended;
i,j,n,temp:word;
begin
readln(n);
b[1]:=0;
for i:=1 to n do
begin
readln(a[i],temp);
b[i+1]:=b[i]+temp;
end;
b[n+1]:=b[n+1]-b[n];
min:=9999999999;
for i:=1 to n do
begin
s:=0;
for j:=1 to i-1 do
begin
temp1:=b[i]-b[j];
temp2:=b[n]-b[i]+b[n+1]+b[j];
if temp1>=temp2 then s:=s+a[j]*temp2 else s:=s+a[j]*temp1;
end;
for j:=i+1 to n do
begin
temp1:=b[j]-b[i];
temp2:=b[i]+b[n+1]+b[n]-b[j];
if temp1>=temp2 then s:=s+a[j]*temp2 else s:=s+a[j]*temp1;
end;
if s<min then min:=s;
end;
writeln(min:0:0);