传送门：Problem - D - Codeforces

题目大意：

思路：

尽量要 最大值变小，最小值变大

即求 最大值的最小 和 最小值的最大 -> 二分答案

AC代码：

代码有注释

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{int n; cin >> n;vector<int> a(n + 1), b(n + 1);for (int i = 1; i <= n; i++) cin >> a[i];auto check1 = [&](int limit){// limit 此时就是 最大值的最小值// 经过操作后，若 b[i] <= limit 就是ok的，否则就放弃这个值// 最大值最小for (int i = 1; i <= n; i++) b[i] = a[i];for (int i = 1; i < n; i++){// b[i] 超过 limit ，就要减小 b[i]if (b[i] > limit){b[i + 1] += (b[i] - limit);b[i] = limit;}}for (int i = 1; i <= n; i++){if (b[i] > limit) return false;}return true;};int left = 0; int right = 1e12;while (right > left){int mid = left + right >> 1;if (check1(mid))right = mid;else left = mid + 1;}int ans = left;auto check2 = [&](int limit){// 最小值最大// limit 就是最小值的最大值for (int i = 1; i <= n; i++) b[i] = a[i];for (int i = 1; i < n; i++){if (b[i] > limit){b[i + 1] += (b[i] - limit);b[i] = limit;}}int mn = 2e18;for (int i = 1; i <= n; i++) mn = min(mn, b[i]);// 经过操作后，mn 仍大于 limit ，则可以继续增大limitif (mn >= limit)return true;else return false;};left = 0; right = 1e12;while (right > left){int mid = left + right + 1 >> 1;if (check2(mid))left = mid;else right = mid - 1;}cout << ans - left << endl;
}
signed main()
{int tt; cin >> tt;while (tt--)solve();return 0;
}