如何运用思维和贪心算法求解最大值问题？

2026-05-19 14:431阅读0评论SEO基础
  • 内容介绍
  • 文章标签
  • 相关推荐

本文共计1852个文字，预计阅读时间需要8分钟。

如何运用思维和贪心算法求解最大值问题？

对于刚刚过去的ICPC青岛站，我做一些简单记录。

题目：这是2022年ICPC青岛站的F题。

赛场：在赛场上，我开始尝试了一个贪心策略，但结果出人意料，陷入了困境。我试图改用树形DP，但时间不够，未能完成。

队友提醒：在队友的提醒下，我补充了思路。

对于刚刚过去的ICPC昆明站，做一些小记录。 题面

这是2022年ICPC昆明站的F题。在赛场上，我一开始敲了个贪心，但是出锅了，改敲树形DP，但是时间来不及了。在队友的提醒下补过了这个题，知道解法的我发现我就是个纯纯的老坛……

原题链接在牛客网：F-Find the Maximum_第46届ICPC亚洲区域赛（昆明）(正式赛），需要先登录之后才能访问。下面搬运一下原题面：

A tree with nn vertices is a connected undirected graph with \(n\) vertices and \(n-1\) edges.

You are given a tree with \(n\) vertices. Each vertex has a value \(b_i\). Note that for any two vertices there is exactly one single path between them, whereas a simple path doesn't contain any edge more than once. The length of a simple path is considered as the number of edges in it.

You need to pick up a simple path whose length is not smaller than \(1\) and select a real number \(x\). Let \(V\) be the set of vertices in the simple path. You need to calculate the maximum of \(\frac{\sum_{u\in V}(-x^2+b_{u}x)}{|V|}\).

输入描述

The first line contains a single integer \(n (2\le n \le 10^5)\) , indicating the number of vertices in the tree.

The second line contains \(n\) integers \(b_1,b_2,\cdots,b_n \enspace (10^{-5} \leq b_i \leq 10^{5})\) indicating the values of each vertex.

Each line in the next \(n−1\) lines contains two integers \(u,v\) indicating an edge in the tree.

输出描述

The output contains a single real number, indicating the answer.

如何运用思维和贪心算法求解最大值问题？

Your answer will be accepted if and only if the absolute error between your answer and the correct answer is not greater than \(10^{-4}\).

时空限制

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K

输入

2 3 2 1 2

输出

1.562500

大意

给出一颗无向树，树上的每一个节点都有一个权值\(b_i\)，要求找到一条长度不小于1的简单路径，记路径上的节点的权值的算术平均值为\(t\)，求\(\frac{t^2}{4}\)的最大值。

题解

本题权重可正可负，而最后需要求的式子是平均值的平方，因此在求解的时候需要同时考虑最大和最小两种情况。而要想路径上的节点算术平均值最大，路径的长度只能为1或者2。

为什么呢？假如有一条长度为3的路径\(L:v_1-v_2-v_3-v_4\)，那么我们将其拆分成两条路径\(L_1:v_1-v_2,L_2:v_3-v_4\)，由算术平均的性质，\(L\)包含的节点的算术平均不大于\(L_1,L_2\)包含节点的算术平均的最大值，也不小于其中的最小值。

我们来简单说明一下：假设\(w_i\)代表编号为\(i\)的节点的权值，那么：

$ t=\frac{w_1+w_2+w_3+w_4}{4}=\frac{w_1+w_2+w_3+w_4}{2}\times \frac{1}{2}=(\frac{w_1+w_2}{2}+\frac{w_3+w_4}{2})\times \frac{1}{2}=\frac{t_1+t_2}{2}$

也就是说\(t\)最大当且仅当\(t_1=t_2=t\)，这样我们考虑长度为1的路径即可。同样的，可以将其推广到长度为\(4,5,\dots\)的路径上，它们都可以拆分成两条长度不小于1的路径，权值算术平均在拆分部分算术平均的最大值与最小值之间。因此，要找最大值，只需考虑所有长度为1或者2（即包含2个或者3个节点）的路径即可。由于权值可能为负，因此我们求出最大的正平均权值和最小的负平均权值，然后进行比较即可。

长度为1的路径边读入边处理即可，长度为2的路径可以通过一轮DFS来寻找：若指定一个节点为DFS的起点，则可以按照各节点到起点的距离将其视作一颗有向树，那么长度为2的路径就有两种情况：

（1）当前节点、当前节点的父节点以及当前节点的子节点，路径为父节点-当前节点-子节点

（2）当前节点和它的两个子节点，路径为子节点-当前节点-另一个子节点。

第一种情况可以很方便的枚举，而第二种情况，由于求的是最值，所以我们可以对所有的子节点排序，贪心地选择权值最大的前两个子节点和权值最小的前两个子节点进行讨论就可以了。

对于子节点的排序时间复杂度为\(O(nlogn)\)，DFS遍历全图的复杂度为\(O(n)\)，综合下来时间复杂度为\(O(nlogn)\)，在题目给出的数据范围内可以接受。

代码实现如下：

#include <bits/stdc++.h> #define GRP int T;cin>>T;rep(C,1,T) #define FAST ios::sync_with_stdio(false);cin.tie(0); #define rep(i,a,b) for(int i=a;i<=b;++i) #define rrep(i,a,b) for(int i=a;i>=b;--i) #define elif else if #define mem(arr,val) memset(arr,val,sizeof(arr)) typedef long long ll; typedef unsigned long long ull; using namespace std; int n; double w[100010]; //权值 double ans; vector< vector<int> > e; //vector实现邻接表 int u, v; void dfs(int r, int pre) { //将所有的子节点按照权值排序 sort(e[r].begin(), e[r].end(), [](int a, int b)->bool{ return w[a] > w[b]; }); //如果子节点有至少两个，就考虑子节点-当前节点-子节点这样的路径（以无向树存储，DFS只是视作有向树，因此需要排除掉父节点） if (e[r].size() > 2 || (pre < 1 && e[r].size() > 1)) { int cnt = 0, flag = 0; double cur = w[r]; //挑权值最大的两个节点 while (cnt != 2) { //如果其中一个是父节点 if (e[r][flag] == pre) { ++flag; continue; } cur += w[e[r][flag]]; ++flag; ++cnt; } cur /= 3; ans = max(ans, cur * cur / 4); //更新答案 cnt = 0, flag = e[r].size() - 1; cur = w[r]; //挑权值最小的两个节点 while (cnt != 2) { if (e[r][flag] == pre) { --flag; continue; } cur += w[e[r][flag]]; --flag; ++cnt; } cur /= 3; ans = max(ans, cur * cur / 4); } for (int i : e[r]) { if (i == pre) { continue; //不能回头 } //不是起始节点的情况下，考虑父节点-当前节点-子节点的路径 if (pre > 0) { double t = (w[pre] + w[r] + w[i]) / 3; ans = max(ans, t * t / 4); //更新答案 } dfs(i, r); //继续搜索 } } int main() { FAST cin >> n; e.resize(n + 1); ans = 0; rep(i, 1, n) { cin >> w[i]; } rep(i, 1, n - 1) { cin >> u >> v; e[u].push_back(v); e[v].push_back(u); double t = (w[u] + w[v]) / 2; //长度为1的边读入时就可以进行处理 ans = max(ans, t * t / 4); } dfs(1, -1); //指定起始节点为第一个节点，并且指定其父节点不存在 cout << fixed << setprecision(6) << ans << endl; return 0; } /* _ _ _ _ /\ | | | | | | (_) / \ | | _____ _| |__| | ___ _ __ _ _ __ __ _ / /\ \ | |/ _ \ \/ / __ |/ _ \| '__| | '_ \ / _` | / ____ \| | __/> <| | | | (_) | | | | | | | (_| | /_/ \_\_|\___/_/\_\_| |_|\___/|_| |_|_| |_|\__, | __/ | |___/ */

标签：findTheMaximum题解

相关推荐

182511如何通过SEM策略有效提升网站转化率？182522520表白网站建设与SEO推广，如何有效提升网站流量和排名？182529Apache Tomcat如何实现高效处理高并发网络请求？182531CEPH-2 rbd功能如何深入理解并应用于普通用户集群？182544如何深入探讨敏捷开发的优势与实施策略？182545全网营销新潮盘点，多渠道策略全解析，有哪些可以运用？182553如何利用Notion和豆瓣构建个性化的阅读计划清单？182554如何运用智启笔尖，创作出更加精彩的文字内容呢？182556编码器如何实现电机转速及角度的精确控制？182557如何通过Docker实现镜像提交、数据卷管理及可视化操作？182561macOS逆向工程中，如何深入剖析macOS应用程序的运行机制？182562如何用C语言实现数据结构中的单链表？182570临沂有哪些专业网站建设公司能提供技术支持保障，助力品牌在互联网时代卓越发展？182575SEO优化报价受哪些因素影响？如何精准预算避免踩坑？182579x64 番外篇中，哪些知识是进行铺垫的必要基础？182580HTTPS支持哪些加密算法？

本文共计1852个文字，预计阅读时间需要8分钟。

如何运用思维和贪心算法求解最大值问题？

对于刚刚过去的ICPC青岛站，我做一些简单记录。

题目：这是2022年ICPC青岛站的F题。

赛场：在赛场上，我开始尝试了一个贪心策略，但结果出人意料，陷入了困境。我试图改用树形DP，但时间不够，未能完成。

队友提醒：在队友的提醒下，我补充了思路。

对于刚刚过去的ICPC昆明站，做一些小记录。 题面

这是2022年ICPC昆明站的F题。在赛场上，我一开始敲了个贪心，但是出锅了，改敲树形DP，但是时间来不及了。在队友的提醒下补过了这个题，知道解法的我发现我就是个纯纯的老坛……

原题链接在牛客网：F-Find the Maximum_第46届ICPC亚洲区域赛（昆明）(正式赛），需要先登录之后才能访问。下面搬运一下原题面：

A tree with nn vertices is a connected undirected graph with \(n\) vertices and \(n-1\) edges.

You are given a tree with \(n\) vertices. Each vertex has a value \(b_i\). Note that for any two vertices there is exactly one single path between them, whereas a simple path doesn't contain any edge more than once. The length of a simple path is considered as the number of edges in it.

You need to pick up a simple path whose length is not smaller than \(1\) and select a real number \(x\). Let \(V\) be the set of vertices in the simple path. You need to calculate the maximum of \(\frac{\sum_{u\in V}(-x^2+b_{u}x)}{|V|}\).

输入描述

The first line contains a single integer \(n (2\le n \le 10^5)\) , indicating the number of vertices in the tree.

The second line contains \(n\) integers \(b_1,b_2,\cdots,b_n \enspace (10^{-5} \leq b_i \leq 10^{5})\) indicating the values of each vertex.

Each line in the next \(n−1\) lines contains two integers \(u,v\) indicating an edge in the tree.

输出描述

The output contains a single real number, indicating the answer.

如何运用思维和贪心算法求解最大值问题？

Your answer will be accepted if and only if the absolute error between your answer and the correct answer is not greater than \(10^{-4}\).

时空限制

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K

输入

2 3 2 1 2

输出

1.562500

大意

给出一颗无向树，树上的每一个节点都有一个权值\(b_i\)，要求找到一条长度不小于1的简单路径，记路径上的节点的权值的算术平均值为\(t\)，求\(\frac{t^2}{4}\)的最大值。

题解

本题权重可正可负，而最后需要求的式子是平均值的平方，因此在求解的时候需要同时考虑最大和最小两种情况。而要想路径上的节点算术平均值最大，路径的长度只能为1或者2。

为什么呢？假如有一条长度为3的路径\(L:v_1-v_2-v_3-v_4\)，那么我们将其拆分成两条路径\(L_1:v_1-v_2,L_2:v_3-v_4\)，由算术平均的性质，\(L\)包含的节点的算术平均不大于\(L_1,L_2\)包含节点的算术平均的最大值，也不小于其中的最小值。

我们来简单说明一下：假设\(w_i\)代表编号为\(i\)的节点的权值，那么：

$ t=\frac{w_1+w_2+w_3+w_4}{4}=\frac{w_1+w_2+w_3+w_4}{2}\times \frac{1}{2}=(\frac{w_1+w_2}{2}+\frac{w_3+w_4}{2})\times \frac{1}{2}=\frac{t_1+t_2}{2}$

也就是说\(t\)最大当且仅当\(t_1=t_2=t\)，这样我们考虑长度为1的路径即可。同样的，可以将其推广到长度为\(4,5,\dots\)的路径上，它们都可以拆分成两条长度不小于1的路径，权值算术平均在拆分部分算术平均的最大值与最小值之间。因此，要找最大值，只需考虑所有长度为1或者2（即包含2个或者3个节点）的路径即可。由于权值可能为负，因此我们求出最大的正平均权值和最小的负平均权值，然后进行比较即可。

长度为1的路径边读入边处理即可，长度为2的路径可以通过一轮DFS来寻找：若指定一个节点为DFS的起点，则可以按照各节点到起点的距离将其视作一颗有向树，那么长度为2的路径就有两种情况：

（1）当前节点、当前节点的父节点以及当前节点的子节点，路径为父节点-当前节点-子节点

（2）当前节点和它的两个子节点，路径为子节点-当前节点-另一个子节点。

第一种情况可以很方便的枚举，而第二种情况，由于求的是最值，所以我们可以对所有的子节点排序，贪心地选择权值最大的前两个子节点和权值最小的前两个子节点进行讨论就可以了。

对于子节点的排序时间复杂度为\(O(nlogn)\)，DFS遍历全图的复杂度为\(O(n)\)，综合下来时间复杂度为\(O(nlogn)\)，在题目给出的数据范围内可以接受。

代码实现如下：

#include <bits/stdc++.h> #define GRP int T;cin>>T;rep(C,1,T) #define FAST ios::sync_with_stdio(false);cin.tie(0); #define rep(i,a,b) for(int i=a;i<=b;++i) #define rrep(i,a,b) for(int i=a;i>=b;--i) #define elif else if #define mem(arr,val) memset(arr,val,sizeof(arr)) typedef long long ll; typedef unsigned long long ull; using namespace std; int n; double w[100010]; //权值 double ans; vector< vector<int> > e; //vector实现邻接表 int u, v; void dfs(int r, int pre) { //将所有的子节点按照权值排序 sort(e[r].begin(), e[r].end(), [](int a, int b)->bool{ return w[a] > w[b]; }); //如果子节点有至少两个，就考虑子节点-当前节点-子节点这样的路径（以无向树存储，DFS只是视作有向树，因此需要排除掉父节点） if (e[r].size() > 2 || (pre < 1 && e[r].size() > 1)) { int cnt = 0, flag = 0; double cur = w[r]; //挑权值最大的两个节点 while (cnt != 2) { //如果其中一个是父节点 if (e[r][flag] == pre) { ++flag; continue; } cur += w[e[r][flag]]; ++flag; ++cnt; } cur /= 3; ans = max(ans, cur * cur / 4); //更新答案 cnt = 0, flag = e[r].size() - 1; cur = w[r]; //挑权值最小的两个节点 while (cnt != 2) { if (e[r][flag] == pre) { --flag; continue; } cur += w[e[r][flag]]; --flag; ++cnt; } cur /= 3; ans = max(ans, cur * cur / 4); } for (int i : e[r]) { if (i == pre) { continue; //不能回头 } //不是起始节点的情况下，考虑父节点-当前节点-子节点的路径 if (pre > 0) { double t = (w[pre] + w[r] + w[i]) / 3; ans = max(ans, t * t / 4); //更新答案 } dfs(i, r); //继续搜索 } } int main() { FAST cin >> n; e.resize(n + 1); ans = 0; rep(i, 1, n) { cin >> w[i]; } rep(i, 1, n - 1) { cin >> u >> v; e[u].push_back(v); e[v].push_back(u); double t = (w[u] + w[v]) / 2; //长度为1的边读入时就可以进行处理 ans = max(ans, t * t / 4); } dfs(1, -1); //指定起始节点为第一个节点，并且指定其父节点不存在 cout << fixed << setprecision(6) << ans << endl; return 0; } /* _ _ _ _ /\ | | | | | | (_) / \ | | _____ _| |__| | ___ _ __ _ _ __ __ _ / /\ \ | |/ _ \ \/ / __ |/ _ \| '__| | '_ \ / _` | / ____ \| | __/> <| | | | (_) | | | | | | | (_| | /_/ \_\_|\___/_/\_\_| |_|\___/|_| |_|_| |_|\__, | __/ | |___/ */