Zhan, tired after the contest, gave the only task that he did not solve during the…
- User
Zhan, tired after the contest, gave the only task that he did not solve during the contest to his friend, Sungat. However, he could not solve it either, so we ask you to try to solve this problem.
You are given an array a1,a2,…,an of length n . We can perform any number (possibly, zero) of operations on the array.
In one operation, we choose a position i (1≤i≤n−1 ) and perform the following action:
ai:=ai−1 , and ai+1:=ai+1+1 . Find the minimum possible value of max(a1,a2,…,an)−min(a1,a2,…,an) .
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤105 ). The description of the test cases follows.
The first line of each test case contains an integer n (1≤n≤2⋅105 ).
The second line of each test case contains n integers a1,a2,…,an (1≤ai≤1012 ).
The sum of n over all test cases does not exceed 2⋅105 .
Output For each test case, output a single integer: the minimum possible value of max(a1,a2,…,an)−min(a1,a2,…,an) .
c++ only also ensure correctness
- Assistant
To solve this problem, we'll first interpret the operation and understand its effects on the array. Here is the step-by-step explanation:
Problem Interpretation:
- We are given an array
a[1..n]. - The operation allows us to alter the array elements as follows:
- For
iranging from1ton-1, we can perform:a_i = a_{i+1};- If
i >= 2, thena_{i-1} = a_{i-1} + 1;
- Note: When
i = 1, since there is noa_{i-1}, we only performa_1 = a_2;
- For
- Our goal is to minimize the difference between the maximum and minimum elements after performing any number of operations.
Key Observations:
-
Propagation of Maximum Element:
- We can perform operations to propagate the maximum element (particularly
a_n) to all other elements of the array. - When we perform the operation starting from the end of the array towards the beginning, we effectively copy the value of
a_nto all preceding elements.
- We can perform operations to propagate the maximum element (particularly
-
Incrementing the Minimum Element:
- During the process of propagating the maximum element to the entire array, we also increment the preceding elements (specifically
a_{i-1}) each time we perform an operation. - The total increments to the minimal element
a_{min_pos}isn - min_pos.
- During the process of propagating the maximum element to the entire array, we also increment the preceding elements (specifically
-
Calculation of Minimal Difference:
- The minimal possible difference between the maximum and minimum elements is:
where:result = max(a_i) - (min(a_i) + total_increments_to_min)total_increments_to_min = n - min_posmin_posis the position (index) of the minimal element in the initial array.
- This formula simplifies to:
result = (max(a_i) - min(a_i)) - (n - min_pos) - We need to ensure that the result is not negative since the difference can't be less than zero.
- The minimal possible difference between the maximum and minimum elements is:
Algorithm Steps:
-
Read Input:
- Read the number of test cases and process each test case.
- For each test case, read
nand the arraya[1..n].
-
Find Maximum and Minimum Elements:
- Iterate through the array to find:
max_val: The maximum value amonga_i.min_val: The minimum value amonga_i.min_pos: The position (smallest index) where the minimal elementmin_valoccurs.
- Iterate through the array to find:
-
Compute the Result:
- Use the formula derived to compute the minimal possible difference:
result = max(0, (max_val - min_val) - (n - min_pos)) - The
max(0, ...)ensures the result is not negative.
- Use the formula derived to compute the minimal possible difference:
-
Output the Result:
- For each test case, output the computed
result.
- For each test case, output the computed
Implementation in C++:
Below is the implementation of the above algorithm:
#include <iostream> #include <algorithm> using namespace std; typedef long long ll; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; ll max_val = 0, min_val = 1e12; int min_pos = 0; ll a[n+1]; for (int i = 1; i <= n; ++i) { cin >> a[i]; if (a[i] > max_val) max_val = a[i]; if (a[i] < min_val) { min_val = a[i]; min_pos = i; } } ll result = max(0LL, max_val - min_val - (n - min_pos)); cout << result << '\n'; } return 0; }This code ensures correctness by carefully implementing the derived formula, considering all possible positions where the minimal element can occur.
- We are given an array