公平的分享 (Fair Share, CF1634E)
2022/2/17 6:12:12
本文主要是介绍公平的分享 (Fair Share, CF1634E),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
公平的分享 (Fair Share, CF1634E)
1.5s 256MB
给你\(m(1\leq m\leq 10^5)\)个数组, 第\(i\)个数组\(a_i\)元素个数为\(n_i(2\leq n_i\leq 2\times 10^5,\sum\limits_{i=1}^{m}n_i\leq 2\times 10^5)\), \(n_i\)为偶数. 数组\(a_i\)的所有元素都是\([1,10^9]\)的整数. 一开始你有两个空的可重集\(L\)和\(R\). 对于每个数组\(a_i\), 你需要把\(a_i\)中的一半元素放入\(L\)中, 另一半放入\(R\)中. 你希望将\(m\)个数组分配完后能使得\(L=R\). 如果可能做到, 输出\(YES\)并给出构造, 否则输出\(NO\).
[分析]
首先, 如果有某个数字在所有\(a_i\)中出现的总次数为奇数, 那么答案一定是\(NO\). 以下考虑每个数出现的次数为偶数的情况. 将在所有\(a_i\)中出现的元素离散化以后(设在所有\(a_i\)中出现过的不同元素个数为\(n\)), 则我们得到一个\(m\times n\)的数表\(X\), 其中\(X_{ij}\)表示\(j\)在\(a_i\)中出现的次数. 于是每行每列的和均为偶数.
我们将每一行当作一个点, 每一列也当作一个点, \(X_{ij}\)表示行点\(i\)和列点\(j\)的边的个数. 于是我们得到一个二分图. 由于每个点的度数都是偶数, 因此图中存在欧拉路径. 于是我们可以将图中所有点定向, 使得每个点的出度和入度相同. 我们令由行点指向列点的边对应的数存入集合\(L\), 由列点指向行点的边对应的数存入集合\(R\), 则这样的构造满足要求.
时间复杂度为\(O(m+n+\sum\limits_{i=1}^{m}n_i)\)(如果使用\(unordered\_map\)进行离散化)(\(n\)是所有\(a_i\)中出现过的不同元素个数).
这篇关于公平的分享 (Fair Share, CF1634E)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升