ZeroJudge J536: 不穩定的礦石 (Ore)

題目敘述

每筆測資第一行有兩個正整數N和A，代表有幾個礦石及最強礦石的吸收力。第二行有N個整數代表每一個礦石的能量。最強礦石的能量最高，他可以吸收左邊A/2數量的礦石和右邊A/2數量的礦石，屆時被吸收的礦石能量會歸零。當某一邊的礦石量沒有達到A/2，最強礦石則會在另外一邊將剩餘的數量一併吸收。

範例輸入 #1

3 2

1 5 1

範例輸出 #1

7 0

範例輸入 #2

7 6

22 73 96 100 99 34 14

範例輸出 #2

438 0

範例輸入 #3

5 2

100 1 2 3 5

範例輸出 #3

103 8

範例輸入 #4

6 4

31 26 95 38 57 1612

範例輸出 #4

1828 31

範例輸入 #5

9 4

1 2 55 3 8 7 1 5 25

範例輸出 #5

69 38

範例輸入 #6

9 6

1 2 55 3 8 7 1 5 25

範例輸出 #6

77 30

解題思路

當某一邊的礦石數量不夠時，先宣告一個變數預設為A/2，吸收一個礦石就將變數-1，吸收另外一邊的礦石時將剩餘的變數加到迴圈終止範圍即可。需要注意的是記憶體區段錯誤，可以先進行範圍判定看看是不是有超出陣列範圍。

解題程式碼如下 (僅供參考)：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    int N, A;
    cin >> N >> A;
    vector<long long int>num;
    long long int max = -999;
    int maxpos = 0;
    for (int i = 0; i<N; i++)
    {
        int tmp;
        cin >> tmp;
        num.push_back(tmp);
        if (tmp > max)
        {
            max = tmp;
            maxpos = i;
        }
    }
    if (maxpos - (A/2) >= 0 && maxpos + (A/2) < N)
    {
        for (int i = maxpos-1; i>=maxpos-(A/2); i--)
        {
            num[maxpos] += num[i];
            num[i] = 0;
        }
        for (int i = maxpos+1; i<=maxpos+(A/2); i++)
        {
            num[maxpos] += num[i];
            num[i] = 0;
        }
    }
    else if (maxpos - (A/2) < 0 && maxpos + (A/2) < N)
    {
        int tmp = A/2;
        for (int i = maxpos-1; i>=0; i--)
        {
            tmp--;
            num[maxpos] += num[i];
            num[i] = 0;
        }
        int stop = maxpos+(A/2)+tmp;
        if (stop >= N) stop = N-1;
        for (int i = maxpos+1; i<=stop; i++)
        {
            num[maxpos] += num[i];
            num[i] = 0;
        }
    }
    else if (maxpos - (A/2) >= 0 && maxpos + (A/2) >= N)
    {
        int tmp = A/2;
        for (int i = maxpos+1; i<N; i++)
        {
            tmp--;
            num[maxpos] += num[i];
            num[i] = 0;
        }
        int stop = maxpos-(A/2)-tmp;
        if (stop < 0) stop = 0;
        for (int i = maxpos-1; i>=stop; i--)
        {
            num[maxpos] += num[i];
            num[i] = 0;
        }
    }
    long long int sum = 0;
    for (int i = 0; i<N; i++)
    {
        if (i == maxpos) continue;
        sum += num[i];
    }
    cout << num[maxpos] << " " << sum << "\n";
}