首页 > 代码库 > 【南开OJ2264】节操大师(贪心+二分+并查集/平衡树)
【南开OJ2264】节操大师(贪心+二分+并查集/平衡树)
好久没更新了,今天就随便写一个吧
题目内容
MK和他的小伙伴们(共n人,且保证n为2的正整数幂)想要比试一下谁更有节操,于是他们组织了一场节操淘汰赛。他们的比赛规则简单而暴力:两人的节操正面相撞,碎的一方出局,而没碎的一方晋级(脑补一下端午节的碰鸡蛋游戏>_<)。最后经过数轮淘汰决出冠军“节操大师”。
通过理性的研究,你测算出他们的节操值分别为1,2,...,n,我们不妨称这个值为“硬度”吧。同时你又测出了一个节操常数k:当两个硬度相差超过k的节操相撞时,硬度小的节操必碎;而当两个硬度相差不超过k的节操相撞时,由于现场操作的不确定因素,两个节操都有碎的可能(当然我们假设不会出现两边都碎的情况囧)。
显然,节操值较低的人也许没有任何可能得到冠军。下面就请你预测,这次比赛的冠军“节操大师”的节操最小值为多少。
(n≤131072, 保证n为2的正整数幂)
首先要二分答案,然后从结果考虑,最终假如是X决赛获胜,那么我们贪心地想,让X与他能获胜的节操值最大的人进行半决赛,这样可以达到最优的结果
如果那个人已经参与了比赛,就选第二大的,依次类推。
于是这个题就有了两种做法,一种是用并查集,一种是用平衡树(或者是set)
每次查询后利用并查集并点(logn)或者直接用set删点(logn)
最后的复杂度就是nlognlogn
#include <iostream> #include <vector> #include <cstdio> #include <cstring> #include <set> using namespace std; const int maxn = 131073; vector <int> V; set<int> S; int n, k; bool ok(int u) { S.clear(); for(int i = 0; i <= n; i++) S.insert((-i)); V.clear(); V.push_back(-u); S.erase(-u); while(V.size() != n) { int l = V.size(); for(int i = 0; i < l; i++) { int x = V[i]; int y = *S.lower_bound(x-k); if(y == 0) return false; V.push_back(y); S.erase(y); } //for(int i = 0; i < l; i++) printf("%d ", -V[i]); //cout<<endl; } return true; } int main() { while(cin>>n>>k) { int l = 1, r = n, mid; while(l < r) { mid = (l+r)/2; if(ok(mid)) r = mid; else l = mid+1; } cout<<l<<endl; } }
【南开OJ2264】节操大师(贪心+二分+并查集/平衡树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。