傳送門

1507 酒廠選址

?時間限制: 1 s ?空間限制: 128000 KB ?題目等級 : 黃金 Gold 題解 題目描述?Description

Abstinence（戒酒）島的居民們酷愛一種無酒精啤酒。以前這種啤酒都是從波蘭進口，但今年居民們想建一個自己的啤酒廠。島上所有的城市都坐落在海邊，并且由一條沿海岸線的環島高速路連接。酒廠的投資者收集了關于啤酒需求量的信息，即每天各城市消費的啤酒桶數。另外還知道相鄰城市之間的距離。每桶啤酒每英里的運費是1元。日運費是將所需要的啤酒從酒廠運到所有城市所必需的運費之和。日運費的多少和酒廠的選址有關。投資者想找到一個合適的城市來修建酒廠，以使得日運費最小。

請設計一個程序：從文件bre.in?讀入城市的數目、相鄰兩城市間的距離以及每個城市消費的啤酒桶數，計算最小的日運費，將結果寫到輸出文件bre.out中。

輸入描述?Input Description

第一行是一個整數n（5?<=?n?<=?10000）?，表示城市的數目。?城市沿高速路編號，使得相鄰的城市的編號也相鄰（城市1和n也被認為是相鄰）。?以下的n行，每行有兩個非負整數。第I+1行的數?zi、di分別是城市I每日的啤酒消費量（桶）和從城市I沿高速路到下一個城市的距離（英里）。高速路的總長不會超過65535?英里。每座城市的日消費量不會超過255桶。

輸出描述?Output Description

一個整數，表示所需的最小日運費（元）。

樣例輸入?Sample Input

6

1?2

2?3

1?2

5?2

1?10

2?3

樣例輸出?Sample Output

41

【思路】

說好的標簽是啟發式搜索呢。。。。

思路：暴力

注意：邊是雙向

【code】

#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> using namespace std; #define LL long long LL s[10001],num[10001]; LL ans=1e20,n,l[10001],tot; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&num[i],&l[i]); tot+=l[i]; s[i]=s[i-1]+l[i-1]; } for(int i=1;i<=n;i++) { LL sum=0; for(int j=1;j<=n;j++) { if(i==j)continue; LL dis=abs(s[i]-s[j]); dis=min(dis,tot-dis); sum+=num[j]*dis; } if(sum<ans)ans=sum; } printf("%lld\n",ans); return 0; }

?

轉載于:https://www.cnblogs.com/zzyh/p/6944897.html

總結

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

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