總時間限制: 1000ms 內存限制: 65536kB
描述
海上有一個島，在環海邊上建有一條環島高速公路，沿著公路有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

解析：
下面以第一個村莊作為起始點(數軸零點)，順時針方向為數軸正方向
先計算每個村莊在數軸上的坐標；
利用兩個村莊的坐標可以方便地計算兩個村莊的順時針距離t1；
利用環形公路周長sum和t1可以計算兩個村莊逆時針距離t2；
t1和t2比較小的那一個即為兩個村莊的最短距離。

依次將所有村莊當做建廠點，計算該方案的運費。
枚舉完所有的方案后即可知道最小花費的方案。

本題真實的測試數據肯定沒到10^4，否則本算法復雜度O（n^2）是無法通過的。

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<math.h>
 4 struct obj
 5 {
 6     long long num;//該村莊啤酒需求量
 7     long long dis;//該村莊距離下一個村莊的距離（順時針的下一個村莊）
 8     long long d;  //該村莊距離起始點的距離（相當于順時針坐標）
 9 };
10 int main()
11 {
12     long long n,i,j;
13     struct obj *a;
14     long long sum=0;//環形公路總長
15     long long cost,minCost,minIndex;//某種建廠方案的話費；歷史上各種建廠方案的最小花費
16     long long distance,t1,t2;
17 
18     freopen("data.in","r",stdin);
19     scanf("%lld",&n);
20     a=(struct obj *)malloc(sizeof(struct obj)*n);
21     for(i=0;i<n;i++)
22     {
23         scanf("%lld%lld",&a[i].num,&a[i].dis);
24         sum=sum+a[i].dis;
25     }
26 
27     a[0].d=0;//第一個村莊作為起始點
28     for(i=1;i<n;i++)
29     {
30         a[i].d=a[i-1].d+a[i-1].dis;
31     }
32 
33     minCost=0;
34     for(i=0;i<n;i++)//依次考慮選擇第i個村莊做建廠點
35     {
36         cost=0;
37         for(j=0;j<n;j++)//計算從其他村莊運輸到第i個村的費用
38         {
39             if(j==i) continue;
40             else
41             {
42                 t1=fabs(a[i].d-a[j].d);
43                 t2=sum-t1;
44                 distance=t1<t2?t1:t2;
45                 cost=cost+a[j].num*distance;
46             }
47         }
48         if(cost<minCost||minCost==0) { minCost=cost; minIndex=i; }
49     }
50     printf("%lld,%lld
",minIndex,minCost);
51     return 0;
52 }

總結

以上是生活随笔為你收集整理的19:啤酒厂选址的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。