【BZOJ-2937】建造酿酒厂前缀和 + 展环为链 + 乱搞

2937: [Poi2000]建造酿酒厂

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

Description

Abstinence岛上的居民很喜欢饮用纯酿的啤酒。迄今为止，他们都是从波兰进口啤酒，自己不生产。但今年岛上的一个城市决定建造一个酿酒厂，供给其他城市的啤酒需求。

岛上所有的城市都环绕在海岸线上，相邻两城之间用高速公路连接（也就是说，它们近似分布在一个圆上）。对于建造酿酒厂的城市来说，它将得到的信息是其余城市对于啤酒的日需求量，并且还有一张记载着相邻两城市之间距离的表格。经过计算，每一桶啤酒每英里的运费为一泰勒。每天的成本为所有城市的运费之和，前提是每个城市的日需求量必须得到满足。可以看出，日成本与酿酒厂建造位置是息息相关的。我们的问题是：为投资者找出最理想的酿酒厂位置，使得日成本最小。

Input

第一行包含一个数n，为城市数目，5<=n<=10000（我们假设城市已经沿着海边高速公路顺序编号，为1，2，……，n，对于1<=i<n，编号为i的城市的下一个城市为i+1，而n号城市的下一个城市为1号）。接下来的n行每行包含两个数字。第i+1行的两个数字为，，表示的是i号城市的日需求量，则表示i号城市与它的下一个城市之间的距离（单位：英里）。海边高速公路的总长度不大于1000000英里，所有城市啤酒的日需求量不大于1000。

Output

仅包含一个数，为所求最小的日成本。

Sample Input

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

Sample Output

HINT

Source

Solution

首先展环为链,那么对链进行系列操作就好

发现这个题..其实就是处理前缀和..那么预处理出前缀和..

然后枚举一下即可..其实就是找转折点.. 看逆时针走近还是顺时针走近..

这样乱搞一下就好了..

有一点点坑点.最容易的当然是计算的时候转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
",ans);
    return 0;
}

long long什么的..早就被坑的稀烂了..当然不会再犯