You are given an array a1,a2,…,an of length n . We can perform any number (possibly,…
- User
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) . .
solve with c++ code
- Assistant
Below is a C++ solution for the problem. The key idea is to perform the operation strategically by maintaining a balance between the maximum and minimum values of the array. You should try to minimize the gap between these values through each operation until no further reduction is possible.
#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } // Initialize minValue and maxValue with large and small possible numbers long long minValue = LLONG_MAX; long long maxValue = LLONG_MIN; // First compute the max(min(a[i], a[i+1])) and min(max(a[i], a[i+1])) across the array for (int i = 0; i < n - 1; ++i) { maxValue = max(maxValue, min(a[i], a[i + 1])); minValue = min(minValue, max(a[i], a[i + 1])); } // The answer is the minimum of either maxValue - minValue cout << min(a[n-1] - a[0], minValue - maxValue) << '\n'; } return 0; }Explanation:
-
Input Handling: We read the number of test cases and then for each test case, we read the array.
-
Edge Cases: If the array length
nis 1, the answer is0becausemax(a) - min(a)is always0when there's a single element. -
Iterating Pairs: For each adjacent pair of elements in the array, we calculate two potential values:
- The maximum of the minimum of the pair (
maxValue) which helps to understand how we can balance smaller elements to become larger. - The minimum of the maximum of the pair (
minValue) which helps to understand how we can balance larger elements to become smaller.
- The maximum of the minimum of the pair (
-
Final Calculation: The result for each test case is either the straightforward max difference
a[n-1] - a[0], or the calculatedminValue - maxValue. The minimum of these gives the final reduced difference. -
Time Complexity:
O(n)per test case since each test involves a single pass through the array. This is efficient given the problem constraints.
-
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.