题意：

　　　　有N座环形分布的城市，相邻城市编号相邻，现要建一座酒厂，每个城市对酒的需求不同，每桶酒每千米运费为1元。给定n各城市，所需酒的桶数以及城市间的距离，求酒厂建在哪个城市可使得运费最小。

输入：

　　　　第一行为n，代表城市个数。以下n行分别有两个整数，代表第i个城市每日需酒量和与下一座城市的距离。

输出：

　　　　输出最小运费。

 

　　　　可以使用枚举法，枚举酒厂在各个城市的情况，计算出相应运费得出最小值。也可简化计算，得出建在某一个城市的运费后可以依次推出其他可能的运费。将环形分布的城市根据距离当前酒厂的位置划分为两个区域，ld代表逆时针区域需求量，rd代表顺时针区域需求量，当酒厂从i移动到i+1后，逆时针区域城市到酒厂距离分别增加D，顺时针区域城市则减少D，所以当前运费current = current + D(ld-rd) 。每次移动后，两个区域需要重新划分。

 

#include<iostream>

using namespace std ;

int main(){

    int demand[10000], dist[10000] ;

    int n, i, mid=0, ld=0, rd=0 ;

    int current=0, half, dl=10, s=0, c=0, best ;

    cin >> n ;

    for(i=0; i<n; i++){

        cin >> demand[i] >> dist[i] ;

        c += dist[i] ;

    }

    half = c / 2 ;

    for(i=1; i<n; i++){         //以第一个城市为酒厂所在地

        s += dist[i-1] ;

        if(s<=half){            //小于周长一半,划为顺时针区域

            mid = i ;

            dl = s ;            //标记分界

            current += s*demand[i] ;

            rd += demand[i] ;

        }

        else{                   //否则划为逆时针区域

            current += (c-s)*demand[i] ;

            ld += demand[i] ;

        }

    }

    best = current ;            //假设当前选址为最佳选择

    for(i=1; i<n; i++){         //依次枚举酒厂所在其他城市时的情况

        ld += demand[i-1] ;　　//原酒厂所在城市移入逆时针区域

        rd -= demand[i] ;　　//将酒厂所在城市移出顺时针区域

        dl -= dist[i-1] ;

        current += (ld-rd)*dist[i-1] ;

        while(dl+dist[mid]<=half){

            dl += dist[mid] ;

            mid = (mid+1)%n ;

            current -= (c-dl-dl)*demand[mid] ;

            ld -= demand[mid] ;

            rd += demand[mid] ;

        }

        if(current<best)

            best = current ;

    }

    cout << best << endl ;

    return 0 ;

}