POJ 2231 Moo Volume

POJ 2231 Moo Volume

這題用的是貪心算法來算的，貪心策略如下：

dist數組表示各個牛的位置距第一個牛的距離，當然之前要對牛的位置進行升序排序。

設a為第一頭牛距各頭牛的距離的總和，然後從第二頭牛開始遍歷，假設遍歷到第i頭牛時，那麼標准為：

t=t-(n-i)*d+i*d，

各變量的含義為：t一開始為a，然後每次就是該表達式運算之後的值；

n為牛的總數；

d為第i頭牛和第i-1頭牛之間的距離。這個公式畫圖其實很好理解的。

把所有的t值加起來就是最後的結果。

#include
#include
#include
#include
#include
#include
using namespace std;
const int N=10005;
int dist[N],cow[N];
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        for(int i=0;i