某實驗室正在對一些剛採集回來的礦石,透過特殊儀器作能量放射的觀察。礦石擺放在一條直線上,且相鄰礦石之間的距離為一單位。實驗過程中研究人員發現所有礦石中能量數值最強的礦石會吸收鄰近不定距離礦石的能量,進而增強自己的能量。
令 A 代表能量最強礦石的吸收力,該礦石會吸乾左側和右側距離 A/2 單位內的礦石的能量。若某一側的礦石數目不到 A/2 個,最強礦石還會從另一側吸收不足數量的礦石的能量。
以下舉例說明礦石吸收現象:
A = 4
吸收前:
70 | 50 | 500 | 30 | 30 | 20 | 10 |
吸收後:
0 | 0 | 680 | 0 | 0 | 20 | 10 |
能量最強之礦石為第 3 個,依其特性吸收周遭 4 個礦石的能量 (左側 2 個、右側 2 個)。
請你撰寫一個程式,給定礦石吸收前的狀態,輸出吸收後的最強礦石能量及其它礦石的總能量。
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入第一列有兩個整數 N (1 ≤ N ≤ 500) 和 A (1 ≤ A ≤ 500)。N 代表有多少個礦石,A 代表能量最強礦石的吸收力,且這個數量只會是偶數。 第二列有 N 個整數 Ti (1 ≤ Ti ≤ 6000,i = 1, 2, 3, …, N),表示由左至右第 i 個礦石被吸收前的能量數值。輸入保證能量最強的礦石只會有一個。 | 請輸出兩個整數,第一個整數代表的是最強礦石吸收後的總能量,第二個整數為剩餘未被吸收能量的礦石之數值總和,兩個數字間以一個空白隔開。 |
3 2 1 5 1 | 7 0 |
7 6 22 73 96 100 99 34 14 | 438 0 |
5 2 100 1 2 3 5 | 103 8 |
6 4 31 26 95 38 57 1612 | 1828 31 |
9 4 1 2 55 3 8 7 1 5 25 | 69 38 |
9 6 1 2 55 3 8 7 1 5 25 | 77 30 |
解題思路
當某一邊的礦石數量不夠時,先宣告一個變數預設為 A/2,吸收一個礦石就將變數 -1,吸收另外一邊的礦石時將剩餘的變數加到迴圈終止範圍即可。
需要注意的是記憶體區段錯誤,可以先進行範圍判定看看是不是有超出陣列範圍。
範例程式碼-ZeroJudge J536: 不穩定的礦石 (Ore)
#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";
}
//ZeroJudge J536
//Dr. SeanXD