Codeforces Round 973 (Div. 2) - D题

传送门：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;
}

 

 加练二分：

传送门：Problem - D - Codeforces

题目大意：

 

 思路：

二分 顶点1要加上的值

AC代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N = 2e5 + 10;
int h[N], e[N], ne[N], idx;
int a[N];
void add(int a, int b)
{e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
bool dfs(int u, int limit)
{if( limit > 1e9 ) return false; // 一定要加这个代码，否则就会爆 long long// 所有顶点的值都是 <= 1e9 的，所以 limit 肯定不能大于 1e9if (a[u] < limit){int temp = limit - a[u];limit += temp;}bool flag = false;for (int i = h[u]; i != -1; i = ne[i]){flag = true;int j = e[i];if (!dfs(j, limit)) return false;}if (!flag){if (a[u] >= limit) return true;else return false;}else return true;
}
bool check(int limit)
{for (int i = h[1]; i != -1; i = ne[i]){int j = e[i];if (!dfs(j, limit)) return false;}return true;
}
void solve()
{memset(h, -1, sizeof h); idx = 0;cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 2; i <= n; i++){int fa; cin >> fa;add(fa, i);}int left = 0; int right = 1e9;while (right > left){int mid = left + right + 1 >> 1;if (check(mid)) left = mid;else right = mid - 1;}cout << a[1] + left << endl;
}
signed main()
{int tt; cin>> tt;while(tt--)solve();return 0;
}