The laboratory is conducting observations on some recently collected ores using a special instrument for energy radiation. The ores are arranged in a straight line, with a distance of one unit between adjacent ores. During the experiment, researchers discovered that the strongest ore in terms of energy value would absorb energy from nearby ores at an indefinite distance, thereby enhancing its energy.
Let A represent the absorption power of the strongest ore. This ore will absorb the energy of ores within a distance of A/2 units to its left and right. If there are fewer than A/2 ores on one side, the strongest ore will still absorb energy from the other side to compensate for the insufficient number of ores.
The following example illustrates the phenomenon of ore absorption:
A = 4
Before Absorption:
| 70 | 50 | 500 | 30 | 30 | 20 | 10 |
After Absorption:
| 0 | 0 | 680 | 0 | 0 | 20 | 10 |
The strongest ore is the third one, which can absorb the energy of the surrounding 4 ores (2 on the left and 2 on the right) according to its characteristics.
Please write a program that, given the state before the absorption of energy by the ores, outputs the energy of the strongest ore after absorption and the total energy of the other ores.
Sample Inputs/Outputs
| Sample Input(s) | Sample Output(s) |
|---|---|
| The first line of input consists of two integers, N (1 ≤ N ≤ 500) and A (1 ≤ A ≤ 500). N represents the number of ores, and A represents the absorption power of the strongest ore. This number will only be even. The second line contains N integers T_i (1 ≤ T_i ≤ 6000, i = 1, 2, 3, …, N), representing the energy values of the ores from left to right before absorption. The input guarantees that there is only one strongest ore. | Please output two integers separated by a single space. The first integer represents the total energy absorbed by the strongest ore after absorption, and the second integer represents the total energy sum of the remaining ores that were not absorbed. |
| 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 |
Thought Process
When the number of ores on one side is insufficient, declare a variable initialized to A/2. Decrease the variable by 1 for each ore absorbed. When absorbing ores from the other side, add the remaining variable to the loop termination range.
It's important to watch out for memory segment errors. You can first perform range checking to see if the array index exceeds its bounds.
Sample Code－ZeroJudge J536: Unstable 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