2937: [Poi2000]建造釀酒廠

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?70??Solved:?24
[Submit][Status][Discuss]

Description

Abstinence島上的居民很喜歡飲用純釀的啤酒。迄今為止，他們都是從波蘭進(jìn)口啤酒，自己不生產(chǎn)。但今年島上的一個(gè)城市決定建造一個(gè)釀酒廠，供給其他城市的啤酒需求。 島上所有的城市都環(huán)繞在海岸線上，相鄰兩城之間用高速公路連接（也就是說，它們近似分布在一個(gè)圓上）。對于建造釀酒廠的城市來說，它將得到的信息是其余城市對于啤酒的日需求量，并且還有一張記載著相鄰兩城市之間距離的表格。經(jīng)過計(jì)算，每一桶啤酒每英里的運(yùn)費(fèi)為一泰勒。每天的成本為所有城市的運(yùn)費(fèi)之和，前提是每個(gè)城市的日需求量必須得到滿足。可以看出，日成本與釀酒廠建造位置是息息相關(guān)的。我們的問題是：為投資者找出最理想的釀酒廠位置，使得日成本最小。

Input

第一行包含一個(gè)數(shù)n，為城市數(shù)目，5<=n<=10000（我們假設(shè)城市已經(jīng)沿著海邊高速公路順序編號，為1，2，……，n，對于1<=i<n，編號為i的城市的下一個(gè)城市為i+1，而n號城市的下一個(gè)城市為1號）。接下來的n行每行包含兩個(gè)數(shù)字。第i+1行的兩個(gè)數(shù)字為，，表示的是i號城市的日需求量，則表示i號城市與它的下一個(gè)城市之間的距離（單位：英里）。海邊高速公路的總長度不大于1000000英里，所有城市啤酒的日需求量不大于1000。

Output

僅包含一個(gè)數(shù)，為所求最小的日成本。

Sample Input

6
1 2
2 3
1 2
5 2
1 10
2 3

Sample Output

41

HINT

Source?

Solution

首先展環(huán)為鏈,那么對鏈進(jìn)行系列操作就好

發(fā)現(xiàn)這個(gè)題..其實(shí)就是處理前綴和..那么預(yù)處理出前綴和..

然后枚舉一下即可..其實(shí)就是找轉(zhuǎn)折點(diǎn).. 看逆時(shí)針走近還是順時(shí)針走近..

這樣亂搞一下就好了..

有一點(diǎn)點(diǎn)坑點(diǎn).最容易的當(dāng)然是計(jì)算的時(shí)候轉(zhuǎn)long long..

Code

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int read() {int x=0,f=1; char ch=getchar();while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; } #define maxn 10100 int n,need[maxn<<1],dis[maxn<<1]; long long sumn[maxn<<1],sumd[maxn<<1]; int main() {n=read();for (int ne,dd,i=1; i<=n; i++) ne=read(),dd=read(),need[i+n]=need[i]=ne,dis[i+n]=dis[i]=dd;for (int i=1; i<=n<<1; i++) sumn[i]=sumn[i-1]+need[i];for (int i=1; i<=n<<1; i++) sumd[i]=sumd[i-1]+dis[i-1];long long ans=0,tmp; int po=1;for (int i=2; i<=n; i++) ans+=(long long)need[i]*min(sumd[i],sumd[1+n]-sumd[i]);for (;sumd[po+1]<sumd[n+1]-sumd[po+1]; po++);tmp=ans;for (int i=2; i<=n; i++){tmp+=(long long)dis[i-1]*(sumn[n+i-1]-sumn[po]-(sumn[po]-sumn[i-1])); for(;sumd[po+1]-sumd[i]<sumd[n+i]-sumd[po+1];po++)tmp+=(long long)need[po+1]*(sumd[po+1]-sumd[i]-(sumd[n+i]-sumd[po+1])); ans=min(ans,tmp);}printf("%lld\n",ans);return 0; }

long long什么的..早就被坑的稀爛了..當(dāng)然不會(huì)再犯

轉(zhuǎn)載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5401844.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ-2937】建造酿酒厂 前缀和 + 展环为链 + 乱搞的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。