当前位置: 首页 > news >正文

并查集 D. Shark [Codeforces Round 484(Div. 2)]

一道还行的并查集,刚开始写的以为是带权并查集,写着写着发现其实不用太麻烦
题目大意是:需要找到一个值 k,使得数组中所有小于 k 的数字构成的连通块满足以下条件:

所有连通块的大小相同
连通块的数量尽可能多
在满足前两个条件下,k 的值尽可能小

如何寻找这个 k 呢?
二分显然不行,不满足单调性
那就直接从小到大枚举呗
每次枚举到一个数字,看看它前面后面是不是可以连起来
可以连起来就合并,使用并查集来维护连通块的大小
用map判断连通块大小及数量是否合格
然后扫一遍就做完了

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
#define ffp(x,y,z) for(ll (x)=(y);(x)<=(z);(x++))
#define ll long long int
#define q_ read()
inline ll read()
{ll x = 0, f = 1;char ch = getchar();while (ch < '0' || ch>'9'){if (ch == '-')f = -1;ch = getchar();}while (ch >= '0' && ch <= '9')x = x * 10 + ch - '0', ch = getchar();return x * f;
}void solve()
{int n = q_;vector<int>num(n + 2, 0);vector<int>id(n + 2, 0);vector<int>fa(n + 2, 0);vector<int>sz(n + 2, 0);//以i为根的子树的大小vector<bool>vis(n + 2, 0);map<int, int>ma;//判断答案用的ffp(i, 1, n){num[i] = q_;id[i] = i;fa[i] = i;sz[i] = 1;}auto cmp = [&](int a, int b)->bool{return num[a] < num[b];};sort(id.begin() + 1, id.end() - 1, cmp);auto find = [&](auto&& find, int a)->int{return a == fa[a] ? a : fa[a] = find(find, fa[a]);};int ans = num[id[1]];int lon = 0;ffp(i, 1, n){int x = id[i];//将这个位置的前面和后面连起来vis[x] = 1;sz[x] = 1;ma[sz[x]] += 1;int ba = find(find, min(x + 1, n));//找后一个,合并if (ba != x && vis[ba])//如果是没有出现过的数字,就别合并{ma[sz[x]]--;ma[sz[ba]]--;if (ma[sz[ba]] == 0)ma.erase(sz[ba]);if (ma[sz[x]] == 0)ma.erase(sz[x]);sz[x] += sz[ba];fa[ba] = x;ma[sz[x]]++;sz[ba] = 0;}int fr = find(find, max(x - 1, 1));//找前一个的根,看是谁if (fr != x && vis[fr]){//合并两根ma[sz[fr]] -= 1;ma[sz[x]] -= 1;if (ma[sz[fr]] == 0)ma.erase(sz[fr]);if (ma[sz[x]] == 0)ma.erase(sz[x]);sz[fr] += sz[x];fa[x] = fr;ma[sz[fr]]++;sz[x] = 0;}//记得判断是否删除了某个节点//合并后统计答案if (ma.size()==1){for (auto [v, cnt] : ma){if (cnt > lon){ans = num[x];lon = cnt;}}}}cout << ans+1 << endl;
}int main()
{int t = 1;while (t--){solve();}return 0;
}
http://www.hskmm.com/?act=detail&tid=23663

相关文章:

  • 实用指南:Spark核心技术解析:从RDD到Dataset的演进与实践
  • 随笔0
  • 加密算法基本原理、特点及采用场景
  • Hackersdaddy ROUGE CTF 2025 完整解题记录
  • AI元人文系列:透明推理者——下一代大模型架构设计
  • 个人随笔
  • 实用指南:1、docker入门简介
  • 调试parlant的大模型配置,最终自己动手写了g4f的模块挂载 - 教程
  • PowerShell注意点
  • 太极 - MKT
  • 题解:P12410 「知りたくなかった、失うのなら」
  • unity面向组合开发二:EC的代码实践
  • 《咳咳,未来编程大师,顶尖程序员的第一条博客》
  • CSP-JF36
  • 超越炒作:使用Agentic AI构建系统架构
  • K个节点的组内逆序调整
  • 【任务】自然语言处理——情感分析 <上>
  • 文件目录
  • 【Azure App Service】Root CA on App Service
  • QOJ #8147. Math Exam 题解
  • 10.03模拟赛t3
  • 国庆梦熊集训做题记录
  • 文件的逻辑结构
  • python 肘部法则,判点聚类分为几类,K-means聚类分析
  • AT_abc315_f [ABC315F] Shortcuts
  • 紫外UV固化太阳光模拟器的原理 - 教程
  • 每日一题
  • P5709 【深基2.习6】Apples Prologue / 苹果和虫子
  • 问题表 - microsoft
  • Leetcode 736. Lisp 语法解析