廈大C語言上機 1392 數組的平衡

1392.數組的平衡

時間限制: 1000 MS          記憶體限制: 65536 K

送出數: 11 (0 users)          通過數: 0 (0 users)

問題描述

寫一個函數，計算一個整形數組A的中心分割點。假設某個分割點的下标為k，那麼S1= A[1]+A[2]+…+A[k], S2=A[k+1]+A[k+2]+…+A[n],讓S1和S2差距最小的下标K即為數組A的中心分割點，若有多個中心分割點，選擇值小的。

輸入格式

    第一行輸入一個整數n,代表數組元素個數。（n<=10000）

    第二行輸入n個整數，每個數的範圍[0,1000]。

輸出格式

    輸出題目中所述的中心分割點的值，若有多個中心分割點，選擇值小的。

樣例輸入

   5

   1 1 1 2 3

樣例輸出

3

來源

#include <stdio.h>

#define INF 0x3F3F3F3F
#define ABS(x) ((x) > 0 ? (x) : (-(x)))

int main()
{
    int n;
    int a[10005] = { 0 };
    int summary[10005] = { 0 };
    int sum;
    int min;
    int split_point;
    int diff;
    int i;

    scanf("%d", &n);
    sum = 0;
    for (i = 1; i <= n; ++i)
    {
        scanf("%d", &a[i]);
        sum += a[i];
        summary[i] = sum;
    }

    min = INF;
    split_point = 0;
    for (i = 1; i <= n; ++i)
    {
        diff = ABS(sum - 2 * summary[i]);
        if (diff < min)
        {
            min = diff;
            split_point = i;
        }
    }

    printf("%d\n", split_point);

    return 0;
}