牛客练习赛59 B

链接：https://ac.nowcoder.com/acm/contest/4743/B
来源：牛客网

在牛国有

个小镇编号

。用二维平面来表示每个小镇的位置，第牛客练习赛59 B

个小镇的位置为

。牛能做为牛国的国王，决定给小镇之间建设一些道路，以便于任意小镇之间都能相互到达，在第i个小镇和第j个小镇之间建设一条道路的花费是

但是牛能小气的很，他想最小化建设的费用。

首先想到的是，最小生成树，然而这道题给的内存及其小，用堆优化是超限的，我们叫要再从，路径长短看起，这是一个绝对式，是关于每个点 v[i] = x_i^2 * y_i + y_i^2 * (y_i - 2 * x_i) , 则dis(i, j) = | v[i] - v[j] |，我们注意到

| |a| - |b| | leqslant | a - b | leqslant |a| + |b|, 我们就发现了对于三个点 i,j,k, 则其小生成树花费为 |v[i] - v[j]| + |v[i] - v[k]| (|v[j] - v[i]| + |v[j] - v[k]|、|v[k] - v[i] | + |v[k] - v[j]|) geqslant |v[i] - v[j] - v[j] + v[k]| = |v[j] - v[k]| (|v[i] - v[k]|、|v[i] - v[j]|)，

所以i先排序 v[i]，答案就是 v[n] - v[i] ，（最小生成树过不了）

#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
const int maxn = 1e5 + 5;
 
int t, n, m, tot;
ll a, b, v[maxn];
 
int main()
{
     scanf("%d", &n);
     for (int i = 1; i <= n; ++i)
     {
         scanf("%lld%lld", &a, &b);
         v[i] = a * a * b+ b * b * (b - a* 2);
     }
     sort(v + 1, v + 1 + n);
     printf("%lld", v[n] - v[1]);
     return 0;
}

牛客练习赛59 B

相关推荐