本文正體字版由OpenCC轉換
剛看到這道題有一種似曾相識的感覺，一時以爲這是一個很簡單的題。仔細讀題後發現並不是很容易，而且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