【题解】LuoGu5687:[CSP-SJX2019]网格图

news/2024/10/30 9:35:59/

原题传送门
肯定是让你一排一排的考虑
那就一排一排的考虑

暴力做法就是暴力 k r u s k a l kruskal kruskal,那么怎么把一整排看成一条边?这样就可以满分了
根据 k r u s k a l kruskal kruskal我们可以知道,只要每次选取最小的边还未联通就是最优的
那么就直接一排一排的搞,每次加进来一排值最小的,但是要减去多余的部分(这部分若加入,那么会形成环)

  • 第一次出现横行或列行,全部加
  • 若不是第一次,则看与自己垂直的有几排,只有一排或没有,不会形成环,全加;否则有 x ( x > 1 ) x(x>1) x(x>1)排,则要减去 x − 1 x-1 x1条边

开ll
Code:

#include <bits/stdc++.h>
#define maxn 300010
#define LL long long
using namespace std;
int n, m;
struct node{LL x, opt;
}a[maxn << 1];
LL cnt[2];inline int read(){int s = 0, w = 1;char c = getchar();for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) +(c ^ 48);return s * w;
}bool cmp(node x, node y){ return x.x < y.x; }int main(){n = read(), m = read();for (int i = 1; i <= n; ++i) a[i] = (node){read(), 0};for (int i = n + 1; i <= n + m; ++i) a[i] = (node){read(), 1};sort(a + 1, a + 1 + n + m, cmp);LL ans = 0;for (int i = 1; i <= n + m; ++i){LL num = a[i].opt ? n : m;if (!cnt[a[i].opt]) ans += (num - 1) * a[i].x;else ans += (num - max(1LL, cnt[a[i].opt ^ 1])) * a[i].x;++cnt[a[i].opt];}printf("%lld\n", ans);return 0;
}

http://www.ppmy.cn/news/209552.html

相关文章

LeetCode 5687.执行乘法运算的最大分数

题目描述 给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers &#xff0c;其中 n > m &#xff0c;数组下标 从 1 开始 计数。 初始时&#xff0c;你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作&#xff08;从 1 开始 计数&#xff09;中&#xff0c;需要…

Problem C(HDU-5687)

Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; 1、insert : 往神奇字典中插入一个单词 2、delete: 在神奇字典中删除所有前缀等于给定字符串的单词 3、search: 查询是否在神奇字典中有一个字符串的前缀等于给定的字符…

5687. 执行乘法运算的最大分数

难度中等 给你两个长度分别 n 和 m 的整数数组 nums 和 multipliers &#xff0c;其中 n > m &#xff0c;数组下标 从 1 开始 计数。 初始时&#xff0c;你的分数为 0 。你需要执行恰好 m 步操作。在第 i 步操作&#xff08;从 1 开始 计数&#xff09;中&#xff0c;需要…

HUD 5687(字典树)

反思&#xff1a;之前在删除单词的时候&#xff0c;只是删除掉单词前缀以后的字符&#xff0c;而没有把整个单词都删除掉&#xff0c;导致WA了很多次。 高手请略过... AC代码&#xff1a; #define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<string.h&g…

(转载)基于鱼群算法的函数寻优算法(matlab实现)

1 理论基础 1.1 人工鱼群算法概述 人工鱼群算法是李晓磊等人于2002年提出的一类基于动物行为的群体智能优化算法。该算法是通过模拟鱼类的觅食、聚群、追尾、随机等行为在搜索域中进行寻优&#xff0c;是集群体智能思想的一个具体应用。生物的视觉是极其复杂的&#xff0c;它…

P5687 [CSP-SJX2019] 网格图(Kruskal扩展)

题目链接 Kruskal 思想的扩展&#xff0c;一开始想到了贪心取各行各列中的最小边权&#xff0c;但是没有把握好环的判断问题&#xff0c;只敲了个裸的 Kruskal 水了水&#xff0c;后面参考了洛谷第一篇的题解&#xff0c;其实就是简单地记录一下已经取的行/列的数目就行啦… #…

HDU5687 Problem C【字典树】

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2772 Accepted Submission(s): 768 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; …

HDU 5687 Problem C 字典树

Problem C Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others) Total Submission(s): 2902 Accepted Submission(s): 793 Problem Description 度熊手上有一本神奇的字典&#xff0c;你可以在它里面做如下三个操作&#xff1a; …