cf1626 D. Martial Arts Tournament(枚举)
2022/1/18 6:35:59
本文主要是介绍cf1626 D. Martial Arts Tournament(枚举),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题意:
给定数组,可选 \(x<y\),把小于 \(x\) 的数划为div1,除此之外小于 \(y\) 的数划为div2,剩下的数为div3。现往每组中放入额外的数,使得每组的大小都是2的幂。输出至少要加几个数。
n <= 2e5,1 <= ai <= n
思路:
开桶记录出现次数。枚举加数后div1的大小 \(2^i\) 以及加数后div2的大小 \(2^j\),从左到右尽量填满 \(2^i\),再从左到右尽量填满 \(2^j\) (二分找区间端点),剩下的属于div3。
const int N = 2e5 + 5, M = 18, INF = 0x3f3f3f3f; int n, s[N]; int cal(int x) { //计算x至少加多少才是2的幂 for(int i = 0; ; i++) if((1<<i) >= x) return (1<<i) - x; } int work(int p1, int p2) { //区间划分为[1,p1],[p1+1,p2],[p2+1,n] return cal(s[p1]) + cal(s[p2]-s[p1]) + cal(s[n]-s[p2]); } void sol() { scanf("%d", &n); fill(s, s + n + 1, 0); for(int i = 1, x; i <= n; i++) scanf("%d", &x), s[x]++; for(int i = 1; i <= n; i++) s[i] += s[i-1]; int ans = INF; for(int i = 0; i < M; i++) for(int j = 0; j < M; j++) { int r1 = (1<<i); int p1 = upper_bound(s+1,s+1+n,r1) - s - 1; int r2 = s[p1] + (1<<j); int p2 = upper_bound(s+1,s+1+n,r2) - s - 1; ans = min(ans, work(p1,p2)); } printf("%d\n", ans); }
这篇关于cf1626 D. Martial Arts Tournament(枚举)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-06Package Easy(基于 NSIS 的打包exe安装包工具)使用方法-icode9专业技术文章分享
- 2024-06-06基于 casdoor 的 ELK 开源登录认证解决方案: elk-auth-casdoor-icode9专业技术文章分享
- 2024-05-29Elasticsearch慢查询日志配置
- 2024-05-29揭秘华为如此多成功项目的产品关键——Charter模板
- 2024-05-29海外IDC业务拓展的7大挑战
- 2024-05-29InLine Chat功能优化对标Github Copilot,CodeGeeX带来更高效、更直观的编程体验!
- 2024-05-29CodeGeeX 智能编程助手 6 项功能升级,在Visual Studio插件市场霸榜2周!
- 2024-05-29AutoMQ 生态集成 Apache Doris
- 2024-05-292024年IDC行业的深度挖掘:机遇、挑战与未来展望
- 2024-05-29五款扩展组件齐发 —— Volcano、Keda、Crane-scheduler 等,邀你体验