【问题描述】
戒酒岛的居民们酷爱一种无酒精啤酒。以前这种啤酒都是从波兰进口，但今年居民们想
建一个自己的啤酒厂。岛上所有的城市都坐落在海边，并且由一条沿海岸线的环岛高速路连
接。酒厂的投资者收集了关于啤酒需求量的信息，即每天各城市消费的啤酒桶数，另外还知
道相邻城市之间的距离。每桶啤酒每英里的运费是1 元。日运费是将所需要的啤酒从酒厂运
到所有城市所必需的运费之和，日运费的多少和酒厂的选址有关，投资者想找到一个合适的
城市来修建酒厂，以使得日运费最小。
读入城市的数目、相邻两城市间的距离以及每个城市消费的啤酒桶数，计算最小的日运
费。
【输入】
第一行是一个正整数 n ，表示城市的数目。城市沿高速路编号，使得相邻的城市的编
号也相邻（城市1 和n 也被认为是相邻）。
以下 n 行，每行有两个非负整数。第 i+1 行的数 zi、di 分别是城市 i 每日的啤酒消
费量（桶）和从城市 i 沿高速路到下一个城市的距离（英里）。
【输出】
一行一个整数，表示所需的最小日运费（元）
【数据范围】
数据范围：5<=n<=10000，高速路的总长不会超过1000000 英里，每座城市的日消费量
不会超过1000 桶。
题解：见代码注释
//算法：前缀和 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> using namespace std; int f_l; int all;//all表示公路总长度 long long ans=2305843009213693951;//ans表示答案，取long long极限值 struct Bro//bro结构体包含城市的编号，前缀和，订酒量和与下一个城市的距离 { int num; int bear,far;//当前城市订酒量和与下一个城市的距离 int allfar,allfar2;//城市的距离前缀和（allfar是到城市1，allfar2是到城市n） }; Bro a[11000]; int main() { freopen("bro.in","r",stdin); freopen("bro.out","w",stdout); int n; scanf("%d",&n); for(int i=1;i<=n;i++) { a[i].num=i; scanf("%d%d",&a[i].bear,&a[i].far); a[i].allfar=a[i-1].allfar+a[i-1].far;//算到一号城市的前缀和 all+=a[i].far; } f_l=a[n].far; for(int i=n;i>=1;i--) { a[i].allfar2=a[i+1].allfar2+a[i+1].far;//算到n号城市的前缀和 } for(int i=1;i<=n;i++) { long long cnt=0; for(int j=1;j<=n;j++) { if(i==j) continue;//如果酒厂就建在城市i，不用运输费 if(i<j) { //如果i在酒厂前面，看i~j近还是j~n~1~i近 cnt+=min(a[j].allfar-a[i].allfar,all-(a[j].allfar-a[i].allfar))*a[j].bear; } if(i>j) { //如果i在酒厂后面，看j~i近还是i-n-1-j近 cnt+=min(a[i].allfar-a[j].allfar,all-(a[i].allfar-a[j].allfar))*a[j].bear; } } ans=min(ans,cnt);//打擂台 } printf("%lld",ans); return 0; } /* 6 1 2 2 3 1 2 5 2 1 10 2 3 */