地震物资输送最优解

从5月12日下午地震发生至今已经超过48小时，根据地震救灾的常识推算，未来24小时将是救灾最后的黄金时间。时间在无情的流逝，数以万计的灾民依旧命悬喘息之间。现在，数万军民正日夜奋战在抢救灾民第一线。从人员的组织协调到救灾物资的后援运输，每一个环节都直接关系到救灾的效果好坏。
由于通往各灾区的道路完全中断，大批救援物资只好空投到各个灾区。某军区准备了一批物资, 恰好能均分到处于环形的N个灾区中。遗憾的是，由于余震不断，天气恶劣等原因，落到各灾区的数量不相同。
正如温家宝总理所一再强调的“抢救人的生命，是这次救灾工作的重中之重” 。为了保证救灾的效率不会平白消耗，当地的民间救助组织可以选择将落到自己所在区的物资传送到左边或者右边相邻的灾区。为了公平起见，我们希望通过相邻灾区的相互传送，最终使所有的灾区获得相同数量的物资。假设一个物资从一个灾区传送到另一个灾区付出的代价是1, 问怎样进行传送，使得所付出的总代价最小。
【标准输入】
第一行： N 表示处于环形的灾区数
接下来n行：每行一个整数Ai, 表示第i个灾区得到的物质数量。
【标准输出】
输出只有一个数, 表示传送物资付出的最小总代价
【约束条件】
（1） N<=1000000
（2） Ai>=0, 保证Ai在长整型范围内, Ai的总和在int64/long long范围内.
（3）时间限制： 1000MS
【样例】
标准输入标准输出
4 4
1
2
5
4

本题我也不知道是哪里的OJ上的，题目还是比较简单，看解答吧

#include "stdafx.h"
#include <stdlib.h>
#include <math.h>
#include <windows.h>

int _tmain(int argc, _TCHAR* argv[])
{
    long sum = 0, sumHead = 0, sumTail = 0;
    int N, avg, i, h = 0, t = 0, *head, *tail;
    scanf("%d", &N);
    head = (int*)malloc(N*sizeof(int));
    tail = (int*)malloc(N*sizeof(int));

    //赋值 求平均值
    for(i = 0; i < N; i++)
    {
        scanf("%d", &head[i]);
        tail[i] = head[i];
        sum += head[i];
    }
    avg = sum/N + (N < (sum%N)*2 ? 1 : 0);

    //计算 计时开始
    SYSTEMTIME tmStart, tmEnd;
    GetLocalTime(&tmStart);

    int n = N - 1;
    for(i = 0; i < n; i++)
    {
        h = head[i] - avg;
        head[i+1] += h;
        sumHead += abs(h);

        t = tail[(N-i)%N] - avg;
        tail[n-i] += t;
        sumTail += abs(t);
    }
    GetLocalTime(&tmEnd);
    //计时结束

    printf("%d\\n时间:%ld毫秒\\n", sumHead<sumTail?sumHead:sumTail, tmEnd.wMilliseconds-tmStart.wMilliseconds);
    free(head);
    free(tail);
    return 0;
}

Xushine

484