深圳广告公司前100名排行,深圳企业seo,wordpress函数手册,沧州网络推广渠成网络传送门#xff1a;Problem - D - Codeforces
题目大意#xff1a; 思路#xff1a;
尽量要 最大值变小#xff0c;最小值变大
即求 最大值的最小 和 最小值的最大 - 二分答案
AC代码#xff1a;
代码有注释
#includebits/stdc.h
using namespace std;
#…传送门Problem - D - Codeforces
题目大意 思路
尽量要 最大值变小最小值变大
即求 最大值的最小 和 最小值的最大 - 二分答案
AC代码
代码有注释
#includebits/stdc.h
using namespace std;
#define int long long
void solve()
{int n; cin n;vectorint 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代码
#includebits/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;
}
