D. Minimize the Difference (Codeforces Round 973 Div. 2)

D. Minimize the Difference

思路：

发现操作是单向的从左往右取高补低，最终目标是尽可能趋于平均，使最大值最小和使最小值最大。可以用二分答案法分别找到两个最值，然后做差即可。

关于这种算法的正确性没有做严格的证明，大概想法是：使最大值最小 和 使最小值最大 是互不冲突且互相促进的。因为在使大值变小的同时，也是在使小值变大，操作过程中都不会对另一个最值产生负影响，只可能产生正的影响。所以两次二分答案得到的两个最值可以在一次操作内同时完成，且为最佳答案。

代码：

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define pb push_back
#define pii pair<int,int>
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
typedef long long ll;
using namespace std;
int a[200005], b[200005];
int n, ans1 = 0, ans2 = 0;

bool check1(int x) {
copy(a + 1, a + n + 1, b + 1); //复制a数组到b数组
for (int i = 1; i <= n; i++) {
if (i == n) {
if (b[i] <= x)
return true;
else return false;
}
if (b[i] > x) {
b[i + 1] += b[i] - x;
}
}
}

bool check2(int x) {
copy(a + 1, a + n + 1, b + 1);
for (int i = n; i >= 1; i--) {
if (i == 1) {
if (b[i] >= x)
return true;
else
return false;
}
if (b[i] < x) {
b[i - 1] -= x - b[i];
}
}
}


void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int l = 1, r = 1e12;
while (l <= r) {
int mid = (l + r) / 2;
if (check1(mid)) {
r = mid - 1;
} else l = mid + 1;
}
ans1 = l;  //最大值的最小
l = 1, r = 1e12;
while (l <= r) {
int mid = (l + r) / 2;
if (check2(mid)) {
l = mid + 1;
} else r = mid - 1;
}
ans2 = r; //最小值的最大
cout << ans1 - ans2 << endl;

}

signed main() {
cin.tie(0)->ios::sync_with_stdio(0);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}

原文地址：https://blog.csdn.net/2303_79310336/article/details/142466538

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！