刚看到这道题有一种似曾相识的感觉，一时以为这是一个很简单的题。仔细读题后发现并不是很容易，而且N<=10000的数据量一般来说只能考虑O(N)的算法和O(NlogN)的算法。
很显然枚举酒厂的建造位置，然后计算的这种O(N^2)的算法是不行的。再次读题，深入挖掘题意中隐含的条件，终于找到一个突破口。由于公 路是一个环，所以每个点到达酒厂的路径要么是顺时针的，要么是逆时针的，而且存在一个分界点，使得分界点两边的城市到酒厂的最短路径一边是顺时针的，另一 边是逆时针的。
想到这里，可以发现O(N^2)的枚举算法大量的时间浪费在计算每个点到酒厂的距离上，因为酒厂每移动一个位置，就要全部算一遍。但是我们发现酒厂每移动到相邻的位置每个点到酒厂的距离的变化是有规律的，基于这种想法，我设计了一种O(N)的算法。
设W[i]为第i个城市的需求量，D[i]为第i个城市到顺时针方向下一个城市的距离。酒厂的位置在A点，分界点为P，则A+1至P-1的 城市到A的最短距离在A的顺时针方向上，记为正方向城市，P至A-1的城市到A的最短距离在A的逆时针方向上，记为负方向城市。记录A到P的正方向距离为 d1，A到P的负方向距离为d2，整个公路周长为C=d1+d2。正方向城市的需求量之和为V1，负方向城市的需求量之和为V2。总的运费为Total。
根据P的定义，可以知道P为分界点时，一定有d1>=d2。如果计算中d1<d2，则需移动P的位置，使得d1>=d2。
P’为P的顺时针方向的下一个城市，当P移动到P’时，Total应减去W[P]*d2，再加上W[P]*d1，因为第P个城市由负方向城市变成了正方向城市。因此V1增加W[P]，V2减少W[P]，d1增加D[P]，d2减少D[P]。
A’为A的顺时针方向的下一个城市，当A移动到A’时，Total增量为(V2-V1+W[A])*D[A]，因为第A个城市加入了负方向 城市，A’城市为酒厂位置，去除它的运费。然后V1减少W[A’]，V2增加W[A]，d1减少D[A]，d2减少D[A]。保留每次求出的Total值 的最小值。
初始时，我们令A为1，P为2，d1为D[1]，d2为Circle-D[1]，首先假设分界点P在第2个城市，即除了A外所有城市都是 负方向城市，依此算出Total的值。然后如果d1<d2，移动P到下一个单位，直到d1>=d2。然后开始移动A的位置，分别算出每次的总 运费，记录最小值。
/*
* Problem: POI2000 bro
* Author: Guo Jiabao
* Time: 2008.12.21 17:28
* State: Solved
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAX=10001;
int D[MAX],W[MAX];
int N,A,P;
long long d1,d2,v1,v2,Circle,Total,Ans;
void init()
{
int i;
freopen("bro.in","r",stdin);
freopen("bro.out","w",stdout);
scanf("%d",&N);
for (i=1;i<=N;i++)
{
scanf("%d%d",&W[i],&D[i]);
Circle+=D[i];
}
}
void movep()
{
int LP=P++;
if (P>N) P=1;
Total+=W[LP]*(d1-d2);
v1+=W[LP]; v2-=W[LP];
d1+=D[LP]; d2-=D[LP];
}
void solve()
{
long long d;
for (int i=N,d=0;i>=2;i--)
{
d+=D[i];
v2+=W[i];
Total+=d*W[i];
}
A=1;P=2;d1=D[1];d2=Circle-D[1];
while (d1<d2)
movep();
Ans=Total;
for (A=2;A<=N;A++)
{
d1-=D[A-1]; d2+=D[A-1];
Total+= D[A-1]*(v2-v1+W[A-1]);
v1-=W[A]; v2+=W[A-1];
while (d1<d2)
movep();
if (Total<Ans)
Ans=Total;
}
}
int main()
{
init();
solve();
printf("%lld",Ans);
return 0;
}
<h2><span class="mw-headline">啤酒厂建造 </span></h2>
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
上次修改时间 2017-02-03