Wannafly 锁
2024-08-24 14:58:31
题意:
现在有 $n$ 个人,每个人有一个已然给定的重要度 $a_i$,现有 K 个锁,每个锁有若干钥匙,分配给一些人,要求一群人能够打开全部 $K$ 把锁,
当且仅当他们重要度的和大于等于 $m$,问最少需要配备多少锁。
解法:
定义极大人群集合为1~n这些人的一个子集,这个集合的人无法打开全部的锁,在这个集合任意添加一个人都能够打开所有的K个锁,这样,ans = 这样的集合个数。
首先考虑对于一个极大集合S,必然是缺 K 种钥匙的其中几种的,如果我们假定是一种钥匙,这样有 [x 持有这种钥匙] = [x ∉ S](充要)。
这样对于每一个极大集合都有一种钥匙来将极大集合内的元素和极大集合外的元素区分开,从而需要配备 cnt(S) 种钥匙。
显然,这也是最少钥匙的方案。
最新文章
- jsonp 演示实例 —— 基于node
- System.exit(0)和System.exit(1)区别
- hbase日常运维管用命令,region管理
- Mac联网恢复系统重新安装Lion
- BZOJ_1009_[HNOI2008]_GT考试_(动态规划+kmp+矩阵乘法优化+快速幂)
- Thrift 应用场景(收集版)
- ubuntu下安装Vmare Workstation,并安装mac补丁
- NLP | 自然语言处理 - 标注问题与隐马尔科夫模型(Tagging Problems, and Hidden Markov Models)
- vim的复制粘贴小结
- 转:Visual Studio进行Web性能测试- Part II
- Quartz源码分析
- 201521123072《Java程序设计》第1周学习总结
- elasticsearch单例模式连接
- 这个接口管理平台 eoLinker 开源版部署指南你一定不想错过
- Python接口测试之对MySQL/unittest框架/Requests 的操作
- UML类图中最重要的几种类关系及其表示
- Python爬虫初学者学习笔记(带注释)
- 分词工具Hanlp基于感知机的中文分词框架
- ARM-ili9325屏调试1--时序
- Mysql知识点个人整理
热门文章
- CentOS 6.5 下安装配置GO 1.2.1
- java获取调用此方法的上面的方法名、类
- Spark Structured Streaming框架(4)之窗口管理详解
- hd acm1048
- bigdecimal类型除法问题
- Outlook 2010打开没反应,只有任务栏有图标的解决方法
- 大话设计模式--备忘录 Memento -- C++实现实例
- Spark- Spark基本工作原理
- spring boot: 一般注入说明(五) @Component, application event事件为Bean与Bean之间通信提供了支持
- UTF-8 delphi 函数