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) .
help out god use c++ and give proof also
- Assistant
To solve this problem efficiently, we'll approach it by observing the constraints and understanding the effect of the given operation.
Key Observations:
- Operations can only reduce
a_ito equala_{i-1}while increasinga_{i+1}by 1. - After performing these operations, the array elements from
a_1toa_{n-1}can be made less than or equal toa_{n-1}and potentially minimized to the smallest value among them (a_{\min}). - Each time we reduce
a_i(by setting it toa_{i-1}), we introduce a "+1" increment that may propagate toa_n. This accumulation affects the final value ofa_n.
Based on these observations, we aim to minimize the maximum difference between any two elements in the array. The minimal possible difference is determined by computing the expression
a_n + total_increments - a_min, where:a_minis the minimum value among the firstn - 1array elements.total_incrementsis the total number of times we perform the operation, which corresponds to the number of times an element in positions2ton-1is greater than its previous element.
Algorithm Steps:
-
Initialize variables:
total_increments = 0a_prev = a[1]a_min = a[1]
-
Iterate over the array from position
2ton - 1:- If
a[i] > a_prev:- We need to perform an operation to reduce
a[i]to matcha_prev. - Increment
total_incrementsby 1.
- We need to perform an operation to reduce
- Else:
- Update
a_prevtoa[i]because no operation is needed.
- Update
- Update
a_minto the minimum ofa_minanda_prev.
- If
-
Compute the minimal possible difference:
- The final value of
a_nisa[n] + total_increments. - The minimal possible difference
Dis the difference between this adjusteda_nanda_min:D = max(a[n] + total_increments - a_min, 0)
- The final value of
-
Output
Das the minimal possible difference.
Proof of Correctness:
- Reducing
a_itoa_{i-1}ensures that the array becomes non-increasing up toa_{n-1}. - Each increment comes from an operation that reduces an element and increases the next one. This affects
a_ncumulatively. - By minimizing
a_{n-1}toa_min, we control the lower bound of the array. - The minimal difference is then the maximum of zero and the adjusted
a_nminusa_min.
Below is the implementation of the above algorithm in C++:
#include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; void solve() { int t; cin >> t; while (t--) { int n; cin >> n; vector<ll> a(n + 1); for (int i = 1; i <= n; ++i) cin >> a[i]; ll total_increments = 0; ll a_prev = a[1]; ll a_min = a[1]; for (int i = 2; i <= n - 1; ++i) { if (a[i] > a_prev) { total_increments += 1; // a_prev remains the same } else { a_prev = a[i]; } a_min = min(a_min, a_prev); } ll D = max(a[n] + total_increments - a_min, 0LL); cout << D << '\n'; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); solve(); return 0; }This code correctly implements the algorithm and efficiently solves the problem within the given constraints.
- Operations can only reduce