ICPC2022KunMingF

题目大意

给定一个\(n\)个节点的树，每个点有个权值\(b_i\),任选一条路径，路径上的点至少为\(2\)个。求\(max(\sum\frac{-x^2+b_kx}{v})\),其中\(b_k\)是路径上点的权值，\(v\)是路径上点的个数，\(x\)是任意一个自己选择的数。

题目链接

思路

假如\(b_v\)确定了，它是一个一元二次方程，\(x\)是自变量，最大值为\(\sum \frac{b_k^2}{4v^2}\),那么我们只需要最大化\(|\sum \frac{b_k}{v}|\)

即，在树上找一条路径，使得路径上平均权值最大。

一个定理:一段序列，连续取数的话，构成平均值最大数，最多不超过\(3\)个。 题目要求至少为两个点，假如我们超过了\(4\)个点，我们可以把它分成两个\(2\)段，取大的，那么平均值就会变大。 （为什么\(3\)个不能分？因为两个数的平均值可能比那个单个的数小，即中间的数比较小，两边的数比较大，比如3,2,3）。

所以我们只要找到每个点相连的点中，最大值，次最大值。 另外需要注意的是，我们是最大化\(|\sum \frac{b_k}{v}|\)，而权值可能为负数，所以最小值，次最小值也要存下来。

最后依次遍历，求得最大值。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int maxN = 1e5 + 7;
int n, a[maxN];
double avg;
vector<int> g[maxN];

bool cmp(int x, int y)
{
    return a[x] > a[y];
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    for(int i = 1; i < n; ++i) {
        int x, y; scanf("%d%d", &x, &y);
        g[x].push_back(y);
        g[y].push_back(x);
        avg = max(avg, (double)(a[x] + a[y]) * (a[x] + a[y]) / 16);
    }
    for(int i = 1; i <= n; ++i)
        sort(g[i].begin(), g[i].end(), cmp);
    for(int i = 1; i <= n; ++i) 
        if(g[i].size() >= 2) {
            avg = max(avg, (double)(a[i] + a[g[i][0]] + a[g[i][1]]) * (a[i] + a[g[i][0]] + a[g[i][1]])/ 36);
            avg = max(avg, (double)(a[i] + a[g[i][g[i].size() - 1]] + a[g[i][g[i].size() - 2]]) * (a[i] + a[g[i][g[i].size() - 1]] + a[g[i][g[i].size() - 2]]) / 36);
        }
    printf("%lf\n", avg);
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/23/ICPC2022KunMingF/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！