牛客练习赛59-B牛能和小镇

题目链接: https://ac.nowcoder.com/acm/contest/4743/B

在这里插入图片描述

思路

题目读完应该可以晓得这是一道最小生成树的题目,模板题!!作为鲁莽型选手,必定得莽一莽!(QAQ… 内存超限了…
好,没事,还有机会!首先我们分析一下,2点建路的代价为:在这里插入图片描述
我们设X 为
在这里插入图片描述
那么 两点的代价就是| X1 - X2|
然后要任意两点联通,那么对于n个点,我们只需n-1条边即可

代码

  • 鲁莽型代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
typedef long long ll;
//typedef pair<int, int> pri;
typedef pair<ll, ll> prl;
int vis[MAXN];
struct node
{
int x;
int y;
ll val;
};
int findx(int x) {
int k = x, tmp, r;
while(vis[k] != k) {
k = vis[k];
}
r = k, k = x;
while(vis[k] != k) {
tmp = vis[k];
vis[k] = r;
k = tmp;
}
return r;
}
void marge(int a, int b) {
int x = findx(a);
int y = findx(b);
if(vis[x] != y) {
vis[x] = y;
}
}
ll getVal(int x1, int y1, int x2, int y2) {
return abs((x1 * x1 * y1 - x2 * x2 * y2 + y1 * y1 * (y1 - 2 * x1) - y2 * y2 * (y2 - 2 * x2)));
}
int cmp(node a, node b) {
return a.val < b.val;
}
int main() {
ios::sync_with_stdio(false);
int n;
while(cin >> n) {
for(int i = 1; i <= n; i++) vis[i] = i;
vector<node> ve;
vector<prl> nodes;
for(int i = 1; i <= n; i++) {
ll a, b;
cin >> a >> b;
nodes.emplace_back(a, b);
}
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
ve.push_back(node{i, j, getVal(nodes[i].first, nodes[i].second, nodes[j].first, nodes[j].second)});
}
}
sort(ve.begin(), ve.end(), cmp);
ll sum = 0;
int now = 0;
while(n > 1) {
if(findx(ve[now].x) != findx(ve[now].y)) {
sum += ve[now].val;
marge(ve[now].x, ve[now].y);
n--;
}
now++;
}
cout << sum << endl;
}
return 0;
}
  • 思考型
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
typedef long long ll;
typedef pair<int, int> pri;
//typedef pair<ll, ll> prl;

int main() {
ios::sync_with_stdio(false);
int n;
while(cin >> n) {
vector<ll> ve;
for(int i = 1; i <= n; i++) {
ll a, b;
cin >> a >> b;
ve.push_back(a * a * b + b * b * (b - 2 * a));
}
sort(ve.begin(), ve.end());
ll sum = 0;
for(int i = 1; i < n; i++) {
sum += ve[i] - ve[i - 1];
}
cout << sum << endl;
}
return 0;
}

本文标题:牛客练习赛59-B牛能和小镇

文章作者:HKer_YM

发布时间:2020年03月18日 - 20:38:08

最后更新:2020年03月18日 - 20:38:44

原始链接:https://blog.dreams-wj.top/2020/03/18/%E7%89%9B%E5%AE%A2%E7%BB%83%E4%B9%A0%E8%B5%9B59-B%E7%89%9B%E8%83%BD%E5%92%8C%E5%B0%8F%E9%95%87/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。