【ICPC】2022 昆明站 F题 题解

【ICPC】2022 昆明站 F题 题解,第1张

题目大意

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

题目链接

思路

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

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

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

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

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

代码
#include 
#include 
#include 
#include 
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;
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/727580.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-26
下一篇 2022-04-26

发表评论

登录后才能评论

评论列表(0条)

保存